基本概念

质数的定义

在>=1的自然数中，除了1和它本身之外不再有其他因数的自然数。
注：<=1，既不是质数，也不是合数，质数也称素数。

质数的性质

素数的因数都成对出现，若d可整除n，则(n/d)也可整除n，只需判断一对因数中小的那个即可。
`注：利用此性质可以优化质数判定算法，将时间复杂度从O(n)降为O(sqrt(n))。

质数的判定

定义法O(n)

bool is_prime(int n){
    if(n<2) return 0;
    for(int i=2;i<n;i++) if(n%i==0) return 0;
    return 1;
}

试除法O(sqrt(n))

bool is_prime(int n){
    if(n<2) return 0;
    for(int i=2;i<=n/i;i++) if(n%i==0) return 0;
    return 1;
}
//循环判断条件若为:i<=sqrt(n),sqrt函数太慢不推荐
//循环判断条件若为:i*i<=n,存在溢出风险

分解质因数O(sqrt(n))

n至多只包含一个大于sqrt(n)的质因子，若有2个，相乘大于n

void divide(int n){
    for(int i=2;i<=n/i;i++)
        if(n%i==0){
            int s=0;
            while(n%i==0){
                n/=i;
                s++;
            }
            printf("%d %d\n",i,s);
        }
    if(n>1) printf("%d %d\n",n,1);
}

筛质数

朴素筛法O(nlongn)

int cnt=0;//质数个数
int primes[N];//质数数组
int st[N];//状态数组，当前数是否为质数，0是，1不是

void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=i+i;j<=n;j=j+i) st[j]=1;
    }
}

埃式筛法O(nlonglogn)

void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            //只筛掉质数的倍数
            for(int j=i+i;j<=n;j=j+i) st[j]=1;
        }
    }
}

线性筛法O(n)

void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=1;
            if(i%primes[j]==0) break;
        }
    }
}