素数筛(算法篇)

算法之素数筛

素数筛

引言：

• 素数(质数)：除了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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

欧拉筛(线性筛)

概念：

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

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

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

算法具体操作：

1. 初始化一个标记数组vis[]和记录素数数组prime，vis所有元素初始化为false
2. 从2遍历到n(要筛选素数范围)，如果vis[i]为false，则将i标记为素数，并将i记录在prime数组中，并将i的倍数j(j=i*i，i*i+i…)标记为合数(true)
3. 遍历完所有的数后，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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

尾言

完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看，或者在github库中自取(包含源代码)

• 博客1： codebooks.xyz
• 博客2：moonfordream.github.io
• github项目地址：Data-Structure-and-Algorithms