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

6
10 2 3 5 4 2

输出样例 #1

3

输入样例 #2

4
100 100 100 100

输出样例 #2

1

输入样例 #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 $ .