codeforces 1047C. Enlarge GCD（数学）

题意：

给出n个数，求出最少删除几个数可以扩大最大公因子。

AC代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<iterator>
using namespace std;
int s[300009],pri[4000];
int cnt;
map<int,int> mp;
map<int,int>::iterator it;
int gcd(int a,int b)
{
  if(b==0)
        return a;
  else
  return gcd(b,a%b);
}

void isprime()
{
  bool prime[4000];
  memset(prime,1,sizeof(prime));
  for(int i=2;i<3880;i++)
  {
    if(prime[i])
           {
      pri[cnt++]=i;
      mp[i]=0;
      for(int j=i+i;j<3880;j+=i)
      {
        prime[j]=false;
      }
    }
  }
}

int main()
{
  int n,t;
  mp.clear();
  cnt=0;
  isprime();
  scanf("%d",&n);
  scanf("%d",&s[0]);
  t=s[0];
  for(int i=1;i<n;i++)
  {
    scanf("%d",&s[i]);
    t=gcd(t,s[i]);
  }
  for(int i=0;i<n;i++)
  {
    s[i]/=t;
  }
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<cnt;j++)
    {
      if(s[i]%pri[j]==0)
      {
        mp[pri[j]]++;
        while(s[i]%pri[j]==0)
        {
          s[i]/=pri[j];
        }
      }
    }
    if(s[i]>1)
    {
      if(mp.count(s[i])==0)
      {
        mp[s[i]]=1;
      }else
      {
        mp[s[i]]++;
      }
    }
  }
  int ans=-1;
  for(it=mp.begin();it!=mp.end();it++)
  {
    ans=max(ans,it->second);
  }
  if(ans!=0)
  printf("%d\n",n-ans);
  else
  printf("-1\n");
  return 0;
}