chocolate
We have a list x_{1},...,x_{N}
of pairwise different positive numbers.
In one step we choose a number a from the list. We delete a and exchange for a
chocolate if there is a b in the remaining list that divides a.
This step can be repeated as long as we find appropriate numbers in the remaining list.
What is the maximal amount of chocolate that we can get this way?
Example
N=9
the list: 12,5,7,8,9,3,11,2,4
12 : chocolate (divisible by 2)
5 : -
7 : -
8 : chocolate (divisible by 2)
9 : chocolate (divisible by 3)
1 : -
3 : -
11 : -
2 : -
4 : chocolate (divisible by 2)
Input Specification
N
x_{1} ... x_{N}
The first line is the number 1 ≤ N ≤ 10^{5}
. The second row is the members of the list
separated by space. The numbers in the list are pairwise different integers between
2
and 10^{6}
Output Specification
M
A single line with the number M
.
Sample Input 1
9
12 5 7 8 9 3 11 2 4
download as text file
Sample Output 1
4
download as text file
Sample Input 2
9
124 58 23 38 6 7 11 13 17
download as text file
Sample Output 2
0
download as text file