-
前置:
-
埃氏筛法
-
直接举例子(从 2~n)
2 是质数,而 4、6、8 不是
3 是质数,6、9 不是
4 不是质数
5 是质数
6 不是质数
7 是质数
8 不是质数
9 不是质数说明:从 2 开始遍历开始筛,那么当遍历到一个数时它还没有被筛掉,它就一定是质数——因为说明在它之前它没有被质因数筛过。
-
上代码
#include<iostream> using namespace std; const int N = 1000010; int primes[N], cnt; //存筛出来的质数 bool st[N];//初始为false,置st[x] = true说明x是合数 void get_primes(int n) { for (int i = 2; i <= n; i ++){ if(st[i]) continue; primes[cnt++] = i; for(int j = i; j <= n; j += i) { st[j] = true; } } } int main() { int n; cin >> n; get_primes(n); cout << cnt << endl; return 0; }
-
时间复杂度
-
O(nlogn)
-
计算过程
void get_primes(int n) { for (int i = 2; i <= n; i ++){ if(st[i]) continue; //n次 primes[cnt++] = i; //n次 for(int j = i; j <= n; j += i) //次数是n/i次 { st[j] = true; } } } //n + n + n/1 + n/2 + ... + n/n = 2n + O(nlogn)
-
-
缺点——从上面的例子中能够看出来,有的数会被筛多次,比如 6 被 2 和 3 各筛过一次。而线性筛就是优化了这个问题
-
-
线性筛法
-
算法特性:每个数都只会被自己的最小质因数筛、且只筛一次。
-
因为比较抽象,直接上代码,仔细讲解代码
void get_primes(int n) { for(int i = 2; i <= n; i ++){ //保证每个数都会过一遍 if(!st[i]) primes[cnt ++] = i; //如果此前没有被筛过说明它就是质数 for(j = 0; primes[j] <= n/ i; j ++){ st[primes[j] * i] = true; if(i % primes[j] == 0) break; } } }
-
时间复杂度
-
O(n)
-
计算过程
void get_primes(int n) { for(int i = 2; i <= n; i ++){ if(!st[i]) primes[cnt ++] = i;//执行n遍 for(j = 0; primes[j] <= n/ i; j ++){ //因为线性筛的特点,这里i从2到n也就会执行n遍 st[primes[j] * i] = true; if(i % primes[j] == 0) break; } } } //n + n = 2n
-
-
质数筛法
-
数学
32 引用 • 86 回帖 • 3 关注
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于