埃式筛法、线性筛法素数 _整数

文章目录
素数判断方法
最简单的就是从 2 ~ n-1 都去与 n 取余，看是否能整除。
bool prime(int n){for(int i = 2; i < n; i ++)if(n % i == 0)return true;return false;}
思考一下：其实没有必要枚举所有的比 n 小的数， n % i == 0 ，那么必定有一个 j 使得 i * j = n 。所以只需要枚举 i * i ≤ n 的 i 就可以了。
bool prime(int n){for(int i = 2; i * i <= n; i ++)if(n % i == 0)return true;return false;}
埃式筛法
如果需要对许多整数进行素数判断，上面得方法时间复杂度就较高了，这就需要更高效的算法，如埃式筛法。
一个数如果是素数，那么它的倍数就一定是合数，这就筛去了它的所有倍数。
操作：将 2 ~ n-1 个整数列出来，从 2 开始把它的倍数都筛去，然后将 3 的倍数筛去……遍历所有的素数，把它的倍数都筛去。
我们设置一个标记数组，依次遍历过去（同时标记它的倍数），若 i 没有被标记就代表 i 不会被 2 ~ i-1 的任何一个整数整除，就说明它是素数。
bool flag[maxx];int prime[maxx], p;//记录素数 void primes(int n){flag[1] = true;for(int i = 2; i <= n; i ++){if(!flag[i]){//找到一个素数 prime[p ++] = i;//记录素数 }for(int j = 0; prime[j] * i <= n; j ++)//遍历素数数组，将全部素数的i倍进行标记 flag[prime[j] * i] = true;}}
时间复杂度：O(n * log log n)
n = 12的埃式筛法流程
本轮筛去的整数
2、3
6、9
2、3
8、12
2、3、5
10
2、3、5

文章插图
12
2、3、5、7
2、3、5、7
2、3、5、7
10
2、3、5、7
11
2、3、5、7、11
12
2、3、5、7、11
线性筛法
仔细思考一下：埃式筛法也有冗余，同一个合数有可能会被两个素数筛。例如， 12：12 % 2 = 0、12 % 3 = 0 ，那么 12 就被 2、3 都筛了一次，这样就导致了重复。
线性筛法保证每个合数只会被它的最小质因数筛去，因此每个数只会被标记一次，时间复杂度是O(n) 。

bool flag[maxx];int prime[maxx], p;//记录素数 void primes(int n){flag[1] = true;for(int i = 2; i <= n; i ++){if(!flag[i]){//找到一个素数 prime[p ++] = i;//记录素数 }for(int j = 0; prime[j] * i <= n; j ++){flag[i * prime[j]] = true;if(i % prime[j] == 0)break;} }}

这与埃式筛法的区别就在于：
if(i % prime[j] == 0)
break;
这样就保证了同一个合数，只会被他最小的质因子筛去。
证明：如果 i % prime[j] = 0 ，记 k = i / prime[j] ，则 i * prime[j + 1] = k * prime[j] * prime[j + 1] ，而 prime[j] < prime[j + 1] ，则代表 prime[j + 1] 不是 i * prime[j + 1] 的最小质因子。
我看一下上面举的例子：12
本轮筛去的整数
2、3
6、9
2、3
8（4 % 2 = 0）
2、3、5
10
2、3、5
12（6 % 2 = 0）
2、3、5、7
2、3、5、7
2、3、5、7
10
2、3、5、7
11
2、3、5、7、11
12
2、3、5、7、11
区间筛法
问题：给定整数 a 和 b ，请问区间 [a, b) 内有多少个素数？
思路：b 以内的合数的最小质因数一定不超过 sqrt(b) 。如果有 sqrt(b) 以内的素数表的话，就可以把埃氏筛法运用在 [a, b) 上了。也就是说，先分别做好 [2, sqrt(b)) 的表和 [a, b) 的表，然后从 [2, sqrt(b)) 的表中筛得素数的同时，也将其倍数从 [a, b) 的表中划去，最后剩下的就是 [a, b) 内的素数了。

埃式筛法、线性筛法 素数

埃式筛法、线性筛法素数