试除法判断质数

$O(n\sqrt{n})$

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

}

埃氏筛质数

$O(nloglogn)$

bool st[N];  //i不是质数,st[i]=true
int prime[N],cnt;  //prime:质数数组  cnt:质数数目

void m1(int n){
    //从2开始
    for(int i=2;i<=n;i++){
        //刚开始2是质数，存进数组
        if(!st[i]){
            prime[cnt++]=i;
            //筛掉质数的倍数（定理：如果一个数可以被之前的质数整除，则它不是质数，否则为质数）
            for(int j=i*2;j<=n;j+=i){
                st[j]=true;
            }
        }

    }
}

线性筛质数

$O(n)$

bool st[N];  //i不是质数,st[i]=true
int prime[N],cnt;

void m2(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) prime[cnt++]=i;

        for(int j=0;prime[j]<=n/i;j++){ //枚举之前选到的质数
            st[prime[j]*i]=true;

            if(i%prime[j]==0) break;

        }
    }
}

分解质因数

$$N= \prod {P_i}^{a_i}$$

其中$P_i$全部为质数

void m3(int n){
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            int cnt=0;
            while(n%i==0){
                cnt++;
                n/=i;
            }
            cout<<i<<' '<<cnt<<endl;
        }
    }
    if(n!=1) cout<<n<<' '<<1<<endl;
}

输入样例

12

输出样例

2 2
3 1

样例解释：$12=2^2*3^1$
⭐⭐if(n!=1) cout<<n<<' '<<1<<endl;