试除法判断质数

分解质因数

int get_primes(int n){
    for(int i = 2;i <= n/i;i++){
        if(n%i==0){
            int k = 0;
            while(n%i==0){
                k++;
                n/=i;
            }
            cout<<i<<" "<<k<<endl;
        }
    }
    if(n>1)  cout<<n<<" "<<1<<endl;
    puts("");
}

埃筛

埃筛，质数的倍数不是质数，埃筛利用这个性质进行筛选。

bool st[1000010];
void get_primes(int n){
    for(int i = 2;i<=n;i++){
        if(!st[i]){
            cout<<i<<endl;
            for(int j=i ;j<=n/i;j++){
                st[j*i]=true;
            }
        }
    }
}

线筛

数论--质数

原文：https://www.cnblogs.com/cqyinsist/p/12743750.html