3150: 数学知识模版

bool primes(int x){
    if(x<2) return false;
    for(int i=2;i<=x/i;i++){
        if(x%i==0) return false;
    }
    return true;
}

int p[N],k,n;
bool f[N];
void primes(int n){ //埃筛，思想：质数的倍数是合数
    for(int i=2;i<=n;i++){
        if(f[i]==0){     //是质数
            p[++k]=i;   //质数存储
            for(int j=i*i;j<=n;j+=i) f[j]=1;
        }
    }
}
/*
内层for优化，即质数的倍数是合数，而合数不用重复枚举；
另外，从i*i开始也是优化步骤
*/

int p[N],k,n;
bool f[N];
void primes(int n){  //埃筛，sqrt(n)次遍历
    for(int i=2;i<=n/i;i++){
        if(f[i]==0){ //是质数
            for(int j=i*i;j<=n;j+=i){
                f[j]=1; 
            } 
        }
    }
    for(int i=2;i<=n;i++){
        if(f[i]==0) p[++k]=i;
    }
}

int p[N],k,n;
bool f[N];
void primes(int n){  //线筛，思想：合数被它最小的质数筛掉
    for(int i=2;i<=n;i++){
        if(f[i]==0) p[++k]=i;  //如果是质数，存储
        for(int j=1;p[j]<=n/i;j++){ //遍历现有质数表
            f[i*p[j]]=1;      //i倍的质数组成的合数
            if(i%p[j]==0) break; //合数被最小的质数筛掉，即合数i%p[j]应该被最小的p[j]筛掉
        }
    }
}

int n,p[N],cnt[N],k;
int decompos(int n){
    int m=0;
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            p[++m]=i;   //存储质数
            while(n%i==0){
                n/=i;
                cnt[m]++;   //存储对应的质数数量
            }
        }
    }
    if(n>1){    //剩余的质数以及数量
        p[++m]=n;
        cnt[m]=1;
    }
    return m;
}