CF#511-C Enlarge GCD（gcd）

题意：给你一个序列，然后求删除几个数之后整个序列的最大公约数增大
思路：1）我们首先要求出这个公共的gcd，然后要使gcd增大1直到到最大的数，然后再统计因子出现的个数，sort用n减去最大
2) 要统计因子，我们还可以使用欧拉筛提前打好素数表，然后把所有数除以gcd剩下的对素数表来求因子个数（每个合数都是某个素数的倍数）
所以我们采用第二种方法，降低复杂度  欧拉筛才O(N)

完整代码：(如果数组大小没有开够给出的可能是WA的结果)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const int maxm = 3e5+5;
const int maxn = 1.5e7+5;
int a[maxm+5],vis[maxn+5],p[maxn+5],s[maxn+5];
int cnt;
int gcd(int x,int y){
    return y? gcd(y,x%y) : x;
}
//欧拉筛
void init(){
    int i ,j;
    cnt = 0;
    memset(vis,0,sizeof(0));
    vis[0] = vis[1] = 1;
    for(i=2;i<=maxn;++i)
    {
        if(!vis[i]) vis[i]= p[cnt++]= i;
        for(j=0;j<cnt&&i*p[j]<=maxm;++j){
            vis[i*p[j]] = p[j];//vis[i+p[j]] = 1;
            if(i%p[j]==0) break;
        }
    }
}
int main()
{
    int n,i,j,g,x,ans;
    init(); 
    scanf("%d",&n);
    g = 0; 
    for(i=1;i<=n;++i) {
        scanf("%d",&a[i]);
        g = gcd(g,a[i]);
    }    
    ans = 0;
    for(i =1;i<=n;i++){
        a[i]/= g;//所有a[i]除以共同gcd(然后记录所有因子个数)
        for(j = 0;p[j]*p[j] <= a[i];j++){
            int q = p[j];
            if(a[i]%q ==0) s[q]++;
            while(a[i]%q==0){
                a[i] /= q;
            }  
        }
        if(a[i] != 1) s[a[i]]++;
    }
    ans = n;
    for(int i=2; i<maxn; ++i){
        ans = min(ans, n-s[i]);
    }
    if(ans == n)    ans = -1;
    printf("%d
", ans);
    return 0;
}