← 返回题目列表

Codeforces · 757/B

B. 巴什的大日子

中文机器翻译题面 查看原题

巴什已经踏上了成为最伟大的神奇宝贝大师的旅程。为了获得他的第一只神奇宝贝,他去了祖鲁教授的实验室。由于巴什是祖鲁教授最喜欢的学生,祖鲁允许他从实验室里拿走尽可能多的神奇宝贝。

但 Zulu 警告他,如果 gcd(s1, s2, s3, ..., sk) = 1,则一组 k > 1 个具有 {s1, s2, s3, ..., sk} 优势的 Pokemon 往往会互相争斗(请参阅 gcd 定义的注释)。

巴什很聪明,不希望他的神奇宝贝互相争斗。然而,他也想最大限度地增加他从实验室带走的神奇宝贝的数量。你能帮助 Bash 找出他最多可以携带的 Pokemon 数量吗?

注意:神奇宝贝不能与自己战斗。

输入

输入由两行组成。

第一行包含一个整数n (1 ≤ n ≤ 105),即实验室中神奇宝贝的数量。

下一行包含 n 个空格分隔的整数,其中第 i 个表示 si (1 ≤ si ≤ 105),即第 i 个神奇宝贝的强度。

输出

打印单个整数 — Pokemons Bash 可以容纳的最大数量。

示例

输入 #1

3
2 3 4

输出 #1

2

输入 #2

5
2 3 4 6 7

输出 #2

3

注意

正整数集合 {a1, a2, ..., an} 的 gcd(最大公约数)是整除所有整数 {a1, a2, ..., an} 的最大正整数。

在第一个示例中,我们可以选择强度为 {2, 4} 的 Pokemon,因为 gcd(2, 4) = 2。

在第二个样本中,我们可以选取强度为 {2, 4, 6} 的 Pokemon,并且不存在 gcd ≠ 1 的更大组。