博主链接

题目

解题思路

题解：先求出元素的最大公因子，开一个数组num记录每个数出现次数，再利用素数筛，求出所有数有当前质数因子的的个数

代码

#include<stdio.h>
#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 gcd(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("%d\n", ans);
	else printf("-1\n");
	return 0;
}