翻译

【问题描述】 在“宠物小精灵”游戏中，Bash想成为精灵大师，他来到Zulu教授的实验室，Zulu教授非常喜欢Bash，他允许Bash随意拿走实验室中的小精灵。

但是Zulu教授警告Bash，每个小精灵都有一个力量值，例如k(k>1)个小精灵在一起，它们的力量值为{s1, s2, s3,…, sk}，如果gcd(s1, s2, s3,…, sk)=1，它们之间就会互相打架，Bash不想他拿走的小精灵互相打架，请问他最多能拿走多少小精灵？

提示：一个小精灵是不会自己打自己的。

【输入格式】 输入包含两行。 第一行一个整数n(1<=n<=10^5)，表示实验室中的小精灵总数。

第二行n个用空格隔开的整数，第i个整数代表第i个小精灵的力量值si(1<=si<=10^5)。

【输出格式】 一行包含一个整数，表示能拿走的小精灵数量最大值。

【输入样例#1】 3 2 3 4

【输出样例#1】 2

【输入样例#2】 5 2 3 4 6 7

【输出样例#2】 3