Paint the Numbers

题面翻译

题目描述

给出一个长度为$n$的序列$a_1,a_2,a_3,...\ ,a_n$，要求你使用最少的颜色对每个染色。对于任何颜色，满足：染成该颜色的数都能被染成该颜色的最小数整除。

比如$[40,60,10]$可以被染成同一种颜色，因为它们都可以被$10$整除。

每种颜色可以使用一次或多次。染成同一个颜色的所有元素不需要是连续的。请求出最少需要的颜色数量。

输入格式

第一行一个正整数$n$，表示序列长度。

第二行$n$个正整数，表示序列的每个元素。

输出格式

一个整数，表示至少需要的颜色数量。

数据范围

$1 \leq n \leq 100$, $1 \leq a_i \leq 100$

样例解释

样例1：$[ {\color{red}{10}}, {\color{blue}{2}}, {\color{orange}{3}},{\color{red}{5}}, {\color{blue}{4}}, {\color{blue}{2}} ]$

样例2：$[ {\color{red}{100}}, {\color{red}{100}}, {\color{red}{100}},{\color{red}{100}} ]$

样例3：$[ {\color{gray}{7}}, {\color{blue}{6}}, {\color{orange}{5}},{\color{red}{4}}, {\color{blue}{3}}, {\color{red}{2}}, {\color{red}{2}}, {\color{blue}{3}} ]$

题目描述

You are given a sequence of integers $a_1, a_2, \dots, a_n$ . You need to paint elements in colors, so that:

• If we consider any color, all elements of this color must be divisible by the minimal element of this color.
• The number of used colors must be minimized.

For example, it's fine to paint elements $[40, 10, 60]$ in a single color, because they are all divisible by $10$ . You can use any color an arbitrary amount of times (in particular, it is allowed to use a color only once). The elements painted in one color do not need to be consecutive.

For example, if $a=[6, 2, 3, 4, 12]$ then two colors are required: let's paint $6$ , $3$ and $12$ in the first color ( $6$ , $3$ and $12$ are divisible by $3$ ) and paint $2$ and $4$ in the second color ( $2$ and $4$ are divisible by $2$ ). For example, if $a=[10, 7, 15]$ then $3$ colors are required (we can simply paint each element in an unique color).

输入格式

The first line contains an integer $n$ ( $1 \le n \le 100$ ), where $n$ is the length of the given sequence.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 100$ ). These numbers can contain duplicates.

输出格式

Print the minimal number of colors to paint all the given numbers in a valid way.

样例 #1

样例输入 #1

6
10 2 3 5 4 2

样例输出 #1

3

样例 #2

样例输入 #2

4
100 100 100 100

样例输出 #2

1

样例 #3

样例输入 #3

8
7 6 5 4 3 2 2 3

样例输出 #3

4

提示

In the first example, one possible way to paint the elements in $3$ colors is:

• paint in the first color the elements: $a_1=10$ and $a_4=5$ ,
• paint in the second color the element $a_3=3$ ,
• paint in the third color the elements: $a_2=2$ , $a_5=4$ and $a_6=2$ .

In the second example, you can use one color to paint all the elements.

In the third example, one possible way to paint the elements in $4$ colors is:

• paint in the first color the elements: $a_4=4$ , $a_6=2$ and $a_7=2$ ,
• paint in the second color the elements: $a_2=6$ , $a_5=3$ and $a_8=3$ ,
• paint in the third color the element $a_3=5$ ,
• paint in the fourth color the element $a_1=7$ .