Bash's Big Day

题意翻译

### 题目描述 Bash已经踏上了成为最伟大的口袋妖怪大师的旅程。为了得到他的第一个口袋妖怪，他去了Zulu教授的实验室。由于Bash是Zulu教授最喜欢的学生，Zulu允许他从实验室里取出任意数量的口袋妖怪。 但是Zulu警告他，每个小精灵都有一个力量值，例如k(k>1)个小精灵在一起，它们的力量值为{s1, s2, s3,…, sk}，如果gcd(s1, s2, s3,…, sk)=1(见GCD的定义注释)，它们之间就会互相打架。 Bash作为一个聪明的人，不希望他的口袋妖怪互相斗争。然而，他也想最大化他从实验室里带走的神奇宝贝的数量。你能帮Bash找出他能带走的最大数量的口袋妖怪吗？ 注意：口袋妖怪不能与自己战斗。 ### 输入输出格式 #### 输入格式： 输入包含两行。 第一行一个整数n(1<=n<=10^5)，表示实验室中的小精灵总数。 第二行n个用空格隔开的整数，第i个整数代表第i个小精灵的力量值si(1<=si<=10^5)。 #### 输出格式： 一行包含一个整数，表示能拿走的小精灵数量最大值。

题目描述

Bash has set out on a journey to become the greatest Pokemon master. To get his first Pokemon, he went to Professor Zulu's Lab. Since Bash is Professor Zulu's favourite student, Zulu allows him to take as many Pokemon from his lab as he pleases. But Zulu warns him that a group of $ k&gt;1 $ Pokemon with strengths $ {s_{1},s_{2},s_{3},...,s_{k}} $ tend to fight among each other if $ gcd(s_{1},s_{2},s_{3},...,s_{k})=1 $ (see notes for $ gcd $ definition). Bash, being smart, does not want his Pokemon to fight among each other. However, he also wants to maximize the number of Pokemon he takes from the lab. Can you help Bash find out the maximum number of Pokemon he can take? Note: A Pokemon cannot fight with itself.

输入输出格式

输入格式

The input consists of two lines. The first line contains an integer $ n $ ( $ 1<=n<=10^{5} $ ), the number of Pokemon in the lab. The next line contains $ n $ space separated integers, where the $ i $ -th of them denotes $ s_{i} $ ( $ 1<=s_{i}<=10^{5} $ ), the strength of the $ i $ -th Pokemon.

输出格式

Print single integer — the maximum number of Pokemons Bash can take.

输入输出样例

输入样例 #1

3
2 3 4

输出样例 #1

2

输入样例 #2

5
2 3 4 6 7

输出样例 #2

3

说明

$ gcd $ (greatest common divisor) of positive integers set $ {a_{1},a_{2},...,a_{n}} $ is the maximum positive integer that divides all the integers $ {a_{1},a_{2},...,a_{n}} $ . In the first sample, we can take Pokemons with strengths $ {2,4} $ since $ gcd(2,4)=2 $ . In the second sample, we can take Pokemons with strengths $ {2,4,6} $ , and there is no larger group with $ gcd≠1 $ .