这道题由于本人水平太菜,线性筛法听了y总的讲解之后反应了很长时间才想明白,特此记录一下。
题目描述
给定一个正整数n,请你求出1~n中质数的个数。
样例
输入样例:
8
输出样例:
4
算法1
(埃氏筛法) $O(nloglogn)$
思路:
从2开始循环至n,判断当前数是否为质数,如果是质数的话,则将质数的数量res+1,并筛除给定范围内以当前质数为倍数的所有数字。
eg
给定范围是8,从2开始枚举
- 2是质数 则筛去8以内2的倍数:4、6、8
- 3是质数 则筛去8以内3的倍数:6
- 4不是质数 跳过
- 5是质数 则筛去8以内5的倍数:无
- 6不是质数 跳过
- 7是质数 则筛去8以内7的倍数:无
- 8不是质数
- 总共4个质数
C++ 代码
int find_primes(int n) {
int cnt;
for(int i = 2; i <= n; i ++) {
if(!st[i]) {
cnt ++;
for(int j = i + i; j <= n; j += i) st[j] = true;
}
}
return cnt;
}
算法2
(线性筛法)
要理解线性筛法首先要始终牢记一点:每个数只能被其最小质因子筛除,举个例子来说,6的质因子有2也有3,但6只能被2筛除。
实现思路:
for(i = 2; i <= n; i ++)
判断i是否为质数,若为质数则存入自定义的质数数组p;
for 遍历质数数组 若i * p[j] > n则结束循环;
筛去i * p[j]; //由于i的增长领先(或者等于)p数组,所以第一次执行时一定保证了最小质因子2可用
if(p[j]是i的最小质因子) 则跳出循环,否则利用下一个质数进行筛取;
直观的算法执行情况可以参考下图:
C++ 代码
void find_primes(int n) {
for(int i = 2; i <= n; i ++) {
if(!st[i]) primes[cnt ++] = i;
for(int j = 0; primes[j] <= n / i; j ++) {
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}