素数判断

@Pelom  October 11, 2021

素数判断

一、素数的定义

质数(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;
        }
    }
}

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


添加新评论