3945. 最大公约数

【题目描述】

给定$n$个正整数$a_1,a_2,\cdots,a_n$，你觉得这$n$个正整数的最大公约数太小了，于是你想通过删除一些数使得剩下的数的最大公因数变大。你现在想知道，你最少需要删掉多少个数？

【输入格式】

第一行包含一个整数$n$。

第二行包含$n$个用空格隔开的正整数，表示$a_1,a_2,\cdots,a_n$。

【输出格式】

一行一个正整数，表示最少要删掉的数的个数。

【输入样例】

4
6 9 15 30

【输出样例】

2

【样例解释】

当前的最大公因数是$3$，删掉$6$和$9$之后剩下的数最大公因数是$15$。

当然，也可以删除$9$和$15$，最大公约数是$6$。

【数据范围与约定】

对于$30\%$的数据，$n\leq 10$；

对于另外$20\%$的数据，$N\leq 3000,a_i\leq 3000$；

对于$100\%$的数据，$n\leq 10^5,1\leq a_i\leq 10^6$，数据保证有解。