757B Bash’s Big Day
题目描述
Bash踏上了成为最强宝可梦训练师的旅程。为了拿到自己的第一只宝可梦，他来到了Zulu教授的实验室。Bash是Zulu教授最喜欢的学生，因此教授允许他想拿多少只就拿多少只。
不过Zulu提醒他，如果一群宝可梦的数量 k > 1，且它们的力量分别为 {s1, s2, s3, …, sk}，那么当 gcd(s1, s2, s3, …, sk) = 1 时，它们往往会彼此打起来（ gcd 的定义见注释）。
Bash很聪明，可不想让自己的宝可梦互相打架；但他也想尽可能多带走一些。你能帮他算出最多可以带走多少只吗？
注意：宝可梦不会和自己打架。
输入格式
输入共两行。
第一行包含一个整数 n（ 1 ≤ n ≤ 105），表示实验室里的宝可梦数量。
第二行包含 n 个以空格分隔的整数，其中第 i 个整数 si（ 1 ≤ si ≤ 105）表示第 i 只宝可梦的力量。
输出格式
输出一个整数 —— Bash最多可以带走的宝可梦数量。
注释
正整数集合 {a1, a2, …, an} 的最大公约数（ gcd ）是能整除其中所有整数 {a1, a2, …, an} 的最大正整数。
在第一个样例中，可以带走力量为 {2, 4} 的宝可梦，因为 gcd(2, 4) = 2。
在第二个样例中，可以带走力量为 {2, 4, 6} 的宝可梦，而且不存在一个更大的队伍满足 gcd ≠ 1。
输入输出样例 #1
输入 #1
输出 #1
输入输出样例 #2
输入 #2
输出 #2