试除法判断质数

分解质因数

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;
            }
        }
    }
}

线筛

bool v[1000010];
int primes[100010],m;
void get_primes(int n){
    for(int i = 2;i<=n;i++){
        if(v[i]==0){
            primes[m++]=i;
        }
        for(int j = 0;primes[j]*i<=n;j++){
            v[primes[j]*i]=1;
            if(i%primes[j]==0) break;
        }
    }
}