[学习] 线性筛+预处理+遍历/分解质因子

写这个是还是从今天那个C题目来的。看正解的时候发现了他用了一个很神奇的遍历质因子的方法，没有多余的操作，就是完全的遍历每一个质因子，只不过需要预先用线性筛处理出来1到n的每一个数字的最小质因子。感觉适用于需要分解多个数字质因子的情况但是我自己写的暴力sqrt(n)貌似也不慢多少就很迷。。。emmmmmm不管了先记下来再说。

#include
using namespace std;
#define MN 300000
#define MX 15000000
int a[MN+5],u[MX+5],p[MX+5],pn,s[MX+5];
int gcd(int x,int y)
{
    return y?gcd(y,x%y):x;
}
int main()
{
    int n,i,j,g,x,ans=0;
    for(i=2; i<=MX; ++i)//线性筛预处理出来p是素数集，u[i]存储的是数字i的最小质因数
    {
        if(!u[i])
            u[i]=p[++pn]=i;
        for(j=1; i*p[j]<=MX; ++j)
        {
            u[i*p[j]]=p[j];
            if(i%p[j]==0)
                break;
        }
    }

    scanf("%d",&n);
    int ma=0;
    for(g=0,i=1; i<=n; ++i)
    {
        scanf("%d",&a[i]),g=gcd(g,a[i]);
        ma=max(ma,a[i]);
    }
    if(ma==g)
    {
        cout<<"-1"<1;)//这里就是神奇的遍历质因子的过程，log(j)的复杂度
            for(++s[x=u[j]]; u[j]==x;)
                j/=u[j];

    for(i=1; i<=pn&&p[i]<=MX; ++i)
        ans=max(ans,s[p[i]]);


    printf("%d",ans?n-ans:-1);
}