Description

 给定n个正整数，a_1,a_2,…,a_n,求最少删去几个数，使得删去后这些数的最大公约数比原先的所有数的最大公约数大。

Input Format

第一行一个整数n，第二行n个正整数，a_1,a_2,…,a_n。

Output Format

一个数，表示最少删去的个数，若无论怎么删都不会比原来的大，输出-1。

3
1 2 4

1

Hint

【输出输出样例1】
</tr> </tbody> </table> 【样例1解释】
删去1这个数，最大公约数从1变到2。
【输出输出样例2】

gcd.in	gcd.out
3 1 2 4 </td>	1

</tr> </tbody> </table> 【样例2解释】
删去6、9，最大公约数从3变到15
【数据范围】
对于30%的数据，n<=15
对于50%的数据，n,a_i<=1000
对于100%的数据，n<=300,000，a_i<=1.5*10^7

Source

素数 筛选法 数学与数论

gcd.in	gcd.out
4 6 9 15 30 </td>	2