素数知识点总结

给出几种算法的参考代码

1、最朴素的素数判定（试除法）

时间复杂度是O(n)

bool IsPrime(int x){
    if(x<=1)
        return false;
    for(int i=2; i<=n; i++){
        if(x%i == 0)
            return false;
    }
    return true;
}

2、开方优化的试除法

时间复杂度试O(logn)

bool IsPrime(int x){
    if(x<=1)
        return false;
    int t = floor(sqrt(x)+0.5);
    for(int i=2; i<=t; i++){
        if(x%i == 0)
            return false;
    }
    return true;
}

区间求素数，一般使用筛法，且比上面求X是否为素数多了n次计算。

3、埃氏筛法

时间复杂度O(nloglogn)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+1;
bool prime[maxn], is_prime[maxn];

void Sieve(int n){ // 2~n范围内的素数 
    memset(is_prime, true, sizeof(is_prime));  // 特例：1不是素数，但是我们不会用到
        int cur = 0;
    for(int i=2; i<=n; i++){
        if(is_prime[i]){
                        prime[++cur] = i;   // 第cur个素数
            for(int j=2*i; j<=n; j+=i) // i的倍数，筛掉 
                is_prime[j] = false; 
        }
    }
}

int main(){
    int n;
    cin >> n;
    Sieve(n);
    return 0;
} 

4、欧拉筛法（线性筛法）

时间复杂度是O(n)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+1;
bool prime[maxn], is_prime[maxn];

void eulerSieve(int n){ // 2~n范围内的素数 
    memset(is_prime, true, sizeof(is_prime));  // 特例：1不是素数，但是我们不会用到 
    int cur = 0;
    for(int i=2; i<=n; i++){
        if(is_prime[i]){ // 记录下素数 
            prime[++cur] = i;
        }
        for(int j=1; j<=cur; j++){
            if(i*prime[j]>n) //超出了n的范围 
                break;
            is_prime[i*prime[j]] = false; // prime[j]的倍数，筛掉 
            if(i%prime[j]==0) // 关键
                break;
        }
    }
}
/*
欧拉筛的思路：在埃氏筛的基础上，优化重复筛选，从而降低时间复杂度，欧拉筛的目标是：一个合数只能被筛掉一次，且是被最小的质因子筛掉。 
欧拉筛的关键： if(i%prime[j]==0)，则 i = k*prime[j]，而如果不break的话，下一个筛掉的数是 i*prime[j+1]。 
而 i*prime[j+1] = (k*prime[j])*prime[j+1]，且prime[j]<prime[j+1]，因此这个数的最小质因子应该是prime[j]。
所以这个数应该被prime[j]筛掉，后续的就不应该再出现了，因此要break结束。 
*/

int main(){
    int n;
    cin >> n;
    eulerSieve(n);
    return 0;
} 

更多资料

1、【素数知识总结】https://blog.csdn.net/u011221820/article/details/78828427
2、【埃氏筛法和欧拉筛法】https://blog.csdn.net/HZEUHJEJNJ/article/details/78658865
3、【欧拉筛法的理解】https://blog.csdn.net/qq_39763472/article/details/82428602

素数知识点总结

原文：https://www.cnblogs.com/gdgzliu/p/12091537.html