1034A - Enlarge GCD - CodeForces Solution

#include <cstdio>
#include <iostream>
const int N	= 1.5e7+10;
using namespace std;

int GCD(int a,int b)
{
	if(a%b==0)return b;
	return GCD(b, a%b);
}

int prime[N],tot = 0;
bool isnp[N];
int minp[N];
void Init()
{
	for(int i = 2;i < N ;i ++)
	{
		if(!isnp[i])
		{
			prime[tot++] = i;
			minp[i] = i;
		}
		for(int j = 0;j < tot;j++)
		{
			int p = prime[j];
			if(p * i >= N)	break;
			isnp[p * i] = 1;
			minp[p * i] = p;
			if(i % p == 0)	break;
		}
	}
}


int cnt[N];

void Spilt(int x)
{
	if(x == 1)
		return;
	int cur = x;
	int last = 0;
	while (cur)
	{
		if(minp[cur] != last)
			 ++cnt[minp[cur]],last = minp[cur];
//		printf("%d\n",minp[cur]);
		if(minp[cur] == cur)
			break;
		cur /= minp[cur];
	}
}

int arr[N];
int n;

void Sol()
{
	for (int i=2; i<=n; i++)
	{
		if(arr[i]!=arr[i-1])
			break;
		else if(i==n)
		{
			printf("-1\n");
			return;
		}
	}
	
	int gcd = arr[1];
	for (int i=1; i<=n; i++)
	{
		gcd = GCD(gcd, arr[i]);
	}
	for (int i=1; i<=n; i++)
	{
		arr[i] /= gcd;
	}
	
	for (int i=1; i<=n; i++)
	{
		if(arr[i] != 1)
			Spilt(arr[i]);
	}
	int maxx = 0;
	for (int i=1; i<N; i++)
	{
		if(cnt[i]<n)
			maxx = max(maxx, cnt[i]);
	}
	int ans = 0;
	if(maxx == 0)
	{
		int minn = 1e9, tot=0;
		for (int i=1; i<=n; i++)
		{
			if(arr[i] < minn)
				minn = arr[i], tot=1;
			else if(arr[i]==minn)
				tot++;
		}
		ans = tot;
	}
	else ans = n-maxx;
	
	printf("%d\n",ans);
}


int main()
{
	Init();
	scanf("%d",&n);
	for (int i=1; i<=n; i++) 
	{
		scanf("%d",&arr[i]);
	}
	Sol();
	
	return 0;
}