1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
|
#include<bits/stdc++.h> #define met(a) memset(a,0,sizeof(a)) #define fup(i,a,n,b) for(int i=a;i<n;i+=b) #define fow(j,a,n,b) for(int j=a;j>0;j-=b) #define MOD(x) (x)%mod using namespace std; const int maxn = 1.5e7 + 10; const int mod = 1e9 + 7; typedef long long ll; int P[maxn], num[maxn], a[300005], p[300005]; int (int a, int b) { if (!b) return a; return gcd(b, a % b); } int main() { int n,d=0; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); num[a[i]]++; if (!d) d = a[i]; else d = gcd(d, a[i]); } int ans = n; for (int i = d + 1; i < maxn; i++) if (!P[i]) { int cnt = 0, j; for (j = i; j < maxn; j += i) P[j] = 1, cnt += num[j]; ans = min(ans, n - cnt); } if (ans < n)printf("%dn", ans); else printf("-1n"); return 0; }
|
近期评论