题面描述

在疫情过后，希望小学的三年二班重新开学。班级任务是将黑板上的 $N$ 个正整数分别上色。为了使黑板报美观且有学习意义，老师规定同种颜色的所有数必须能被该颜色中最小的数整除。你需要计算出最少需要多少种颜色来完成这个任务。

思路

从小到大排序后直接枚举一遍即可，将$n$个数划分为若干子集，标准是是否都能被各自子集的最小整数整除。

cpp

题目描述

疫情过后，希望小学终于又重新开学了，三年二班开学第一天的任务是将后面的黑板报重新制作。

黑板上已经写上了 $N$ 个正整数，同学们需要给这每个数分别上一种颜色。

为了让黑板报既美观又有学习意义，老师要求同种颜色的所有数都可以被这种颜色中最小的那个数整除。

现在请你帮帮小朋友们，算算最少需要多少种颜色才能给这 $N$ 个数进行上色。

输入描述 第一行有一个正整数 $N$，其中。

第二行有 $N$ 个 $int$ 型数(保证输入数据在 $[1,100]$ 范围中)，表示黑板上各个正整数的值。

输出描述

输出只有一个整数，为最少需要的颜色种数。

样例1

输入

3
2 4 6

输出

1

说明

所有数都能被 $2$ 整除

样例2

输入

4
2 3 4 9

输出

2

说明

$2$ 与 $4$ 涂一种颜色，$4$ 能被 $2$ 整除；

$3$ 与 $9$ 涂另一种颜色，$9$ 能被 $3$ 整除。

不能 $4$ 个数涂同一个颜色，因为 $3$ 与 $9$ 不能被 $2$ 整除。

所以最少的颜色是两种。