素数判断

一、素数的定义

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

注意 $1$ 不是素数也不是合数。

二、判断一个数是否为素数

由定义可得，一个数 $n$ 为素数当且仅当它只含因数 $1$ 和它本身。于是可从 $2$ 枚举到 $n-1$ 判断其是否为 $n$ 的因数。

inline bool isPrime(int x){
    if(x==1)
        return 0;
    if(x==2)
        return 1;
    for(int i=2;i<x;i++)
        if(x%i==0)
            return 0;
    return 1;
}

时间复杂度为 $O(N)$ 。

优化（1）

不难发现因数总是成对出现，因此只需枚举到 $\sqrt{n}$ 即可。

inline bool isPrime(int x){
    if(x==1)
        return 0;
    if(x==2)
        return 1;
    for(int i=2;i*i<=x;i++)
        if(x%i==0)
            return 0;
    return 1;
}

时间复杂度为 $O(\sqrt{N})$ 。

优化（2）

初步观察，发现 $2$ 是唯一的偶素数，因此可以先筛去偶数（除 $2$ ）；
进一步观察，一个素数（除 $2$ 与 $3$）不会是 $2$ 与 $3$ 的倍数，因此一个素数（除 $2$ 与 $3$）可以表示为 $6x-1$ 或 $6x+1$ 。

inline bool isPrime(int x){
    if(x==1)
        return 0;
    if(x==2 || x==3)
        return 1;
    if(x%6!=1 && x%6!=5)
        return 0;
    for(int i=5;i*i<=x;i+=6)
        if(x%i==0)
            return 0;
    return 1;
}

时间复杂度为 $O(\frac{\sqrt{N}}{3})$ 。

二、筛法求素数

1、埃拉托斯特尼（Eratosthenes）筛法

由一中的优化(2)启发，可以得出结论素数的倍数一定不是素数。
具体实现为以一个bool数组储存信息，记录是否为素数（ $0/1$ )。从 $2$ 开始将所有 $2$ 的倍数标记为合数，最小的未被标记的数一定为素数，再从这个数开始标记其倍数，直到最后，未被标记的数均为素数。

bool isP[N];
inline void siftPrime(){
    memset(isP,1,sizeof(isP));
    for(int i=2;i<=N;i++)
        if(isP[i])
            for(int j=2;j*i<=N;j++)
                isP[j*i]=0;
}

时间复杂度为 $O(N\log{\log{N}})$ 。

优化

因为比 $i^2$ 小的合数一定含有比 $i$ 小的素因子，也就是说已经被筛过了，于是内部循环可以直接从 $i^2$ 开始筛。

bool isP[N];
inline void siftPrime(){
    memset(isP,1,sizeof(isP));
    for(int i=2;i<=N;i++)
        if(isP[i])
            for(int j=i;j*i<=N;j++)
                isP[j*i]=0;
}

2、欧拉（Euler）筛法

在埃氏筛中，同一个合数可能被筛去多次，这些不必要的判断降低了效率。那么如何保证每个合数只被筛去一次呢？将一个合数分解为最小素因子 $\times$ 一个合数的形式，我们只需要用它的最小素因子筛去它即可，这便是欧拉筛。
用 $pri[]$ 数组记下目前已经筛出的所有素数。对于一个合数 $i$ ，若 $i$ 能整除 $pri[j]$ ($i \mid pri[j]$)，记 $i=k \cdot pri[j]$，则 $$i \cdot pri[j+1]=k \cdot pri[j] \cdot pri[j+1]$$ 含有因子 $pri[j]$ ，不需要再次进行标记，对于其后的素数同理，因此可以在此处直接跳出循环。

bool isP[N];
int pri[N];
inline void siftPrime(){
    for(int i=2;i<=n;i++){
        if(isP[i])
            pri[++cnt]=i;
        for(int j=1;j<=cnt && pri[j]*i<=n;j++){
            isP[pri[j]*i]=0;
            if(i%pri[j]==0)
                break;
        }
    }
}