素数筛(算法篇)

算法之素数筛

素数筛

引言：

素数(质数)：除了1和自己本身之外，没有任何因子的数叫做素数(质数)

朴素筛法(优化版)

概念：

朴素筛法：是直接暴力枚举2到当前判断的数x(不包括)，然后看在这范围内是否存在因子，如果存在就不是素数，不存在就是素数，时间复杂度为O(n*n)
优化版：优化版是用到了一个数学性质进行优化，使其只需要判断2到sqrt(x)的范围内，是否存在x的因子即可，时间复杂度为O(n*sqrt(n))

数学性质：如果一个数x能够被一个大于1且小于等于sqrt(x)的整数整除，那么x必定能够被另一个大于1且大于sqrt(x)的整数整除。

#include <iostream>
using namespace std;

//朴素筛素数判断算法时间复杂度：O(n)
bool isprime1(int x){
    if(x==1) return false;
    if(x==2) return true;
    for(int i=2;i<x;++i){
        if(x%i==0) return false;
    }
    return true;
}

//优化版素数判断算法时间复杂度：O(sqrt(n))
bool isprime(int x){
    if(x==1) return false;
    if(x==2) return true;
    for(int i=2;i<x/i;++i){
        if(x%i==0) return false;
    }
    return true;
}




int main() {
    //假设筛选出1-1000的素数
    for(int i=1;i<=1000;i+=2){
        if(isprime(i)) cout<<i<<endl;
    }
    system("pause");
    return 0;
}

欧拉筛(线性筛)

概念：

欧拉筛：利用合数的数学性质，可以将素数筛的算法优化到时间复杂度为O(n)

合数：除了1和自身之外还有其他正因子(除了 1 和自身以外的能够整除它的正整数)，并且大于1的整数

数学性质：对于任意一个合数 x，它一定可以被其最小质因数(即最小的能整除 x 的质数)整除

算法具体操作：

初始化一个标记数组vis[]和记录素数数组prime，vis所有元素初始化为false
从2遍历到n(要筛选素数范围)，如果vis[i]为false，则将i标记为素数，并将i记录在prime数组中，并将i的倍数j(j=i*i，i*i+i…)标记为合数(true)
遍历完所有的数后，prime数组中的数都为素数

总结：

在这个过程中，每个合数都会被标记为其最小质因数，这样能够确保每个合数只会被标记一次。由于每个合数只会被其最小质因数标记，因此在遍历过程中，每个合数只会被标记一次，而非多次，从而避免了重复标记，提高了效率。

const int N=1e8+10;
int prime[N];
bool vis[N];

//欧拉筛总体时间复杂度为O(n)
void isprimes(int n){
    int cnt=0;
    for(int i=2;i<=n;++i){
        if(!vis[i]) prime[cnt++]=i;
        for(int j=0;prime[j]<=n/i;++j){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}