算法入门 — 素数筛

113 阅读 0 评论 75 点赞

我是靠谱客的博主等待小猫咪，这篇文章主要介绍算法入门 — 素数筛，现在分享给大家，希望可以做个参考。

α. 何谓素数？

素数，也就是我们常说的质数，官方解释为在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数.

β. 如何判断其是否为素数？

β1. 初始版本

由定义知，对于一个自然数n, 如果从 2 - n -1之间的任意数 i，n均不能被 i 整除,则 n 为素数. 于是通过一个很简单的for循环，我们便很容易的写出来最简单的素数判断函数！

复制代码

1
2
3
4
5
6
7
8
bool isPrime(int num){
for(int i = 2;i < num;i++){
if(num % i == 0)
return false;
}
return true;
}

β2. 加强版

我们来接着想一下，如果我们对一个数进行判断，最好情况下是被 2 整除后直接被判断为非素数，最坏情况下为遍历一遍判断为素数，所以在不考虑素数与非素数的个数占比的差异的情况下，我们可以大致认为平均下来时间复杂度为O(n/2).
对于一个自然数 n, 如果存在 a * b == n （a <= b）,那么必定
存在以下结论：

a <= sqrt(n)
b >= sqrt(n)
同时，对于一个合数，例如 :

2 * 6 == 12 6 * 2 == 12

在利用 for 循环进行遍历的时候，如果 3 可以将 12 整除 .那么，就可以认定 12 为合数. 换一种思想，对于一个素数来讲，如果在(int)sqrt(n)+1 之前都没有 i 将其整除，那么之后的 i 也就不会有数据会将其整除，因为如果 6 可以将 12 整除，那么 2 肯定也是可以的. 所以，对于 for 循环的迭代次数我们可以有理论依据的将其减少,得到以下的更高效率的代码

复制代码

1
2
3
4
5
6
7
8
9
bool isPrime(int num){
for(int i = 2;i * i < num;i++){
// i <= (int)sqrt(num) + 1 也可
if(num % i == 0)
return false;
}
return true;
}

γ. 素数筛

γ1. 打表

这个名词对于参加过一些程序设计比赛的同学应该不会陌生，所谓打表就是讲一些数据预先存起来，在程序运行的时候直接访问，得到一个O(1)的可观时间.
就拿我们这个判断素数来说吧，对于一个程序程序设计比赛来说，数据量是比较大的，如果我们在素数问题上一次又一次的判断，那么一般都会TLE的，因此我们引入了这样一个思想——>空间换时间，即使用一个数组来存储每个数的状态（是否为素数），这样就可以实现 O(1) 的时间复杂度了.

复制代码

1
2
int isPrime[10] = {0,1,1,1,0,1,0,1,0,1}; //此处列出了0-9 十个数的素数状态

γ2. 埃氏筛

然而还有一个问题没有解决,对于几十几百的数，我们还是有那么一点点的精力来预先存储每个数的状态的，但对于很大的数据来说，我们还是束手无策的，因此，素数筛就排派上了很大的用场.素数筛有很多种，这里只给大家讲一种最基本的埃氏筛
思路引用了下面这篇博客,以下为核心思想：

想更深层了解请戳这篇博客

从2开始 2是素数那么4不是 6不是 8也不是 10、12、14、16、18、20 都不是这是9次操作
然后 3 开始 6 9 12 15 18 都不是素数这是5次操作
然后4 跳过 5 跳过 6 跳过
从7开始 14 不是素数这是1次操作
后边的 8 9 10 11 12 14 15 16 18 20 都会跳过
而11 13 17 19 都不会操作因为他们的倍数大于20了

其中核心思想是如果一个数确定为素数，那么其倍数（2，3，4，…）都不会为素数！

废话不多说了，还是上代码吧~

复制代码

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
35
36
37
38
39
//
// Created by 29273 on 2020-07-26.
//
#include <iostream>
#include <set>
#include <unordered_map>
#include <map>
#include <cctype>
#include <algorithm>m
#include <string.h>
#include <string>
#include <vector>
#include <cstdio>
using namespace std;
#define maxNum 10000 
int prime[maxNum]; // 将素数从小到大存储起来
bool isPrime[maxNum];
// 存储每一个数
int countN;
void Prime(int n){
//埃氏筛
countN = 0;
for(int i = 2;i <= n;i++){
if(!isPrime[i]){
prime[countN++] = i;
}
for(int j = 2; j * i <= n;j++){
isPrime[j*i] = true;
}
}
}
int main(){
Prime(1000);
for(int i = 0;i <= countN;i++){
printf("%d ",prime[i]);
}
return 0;
}