一 试除法判断质数 O(√n)
质数有一个非常重要的性质, 那就是当 d|n 时, n/d|n 也成立, 其中 d|n表示 d 能被 n 整除, 比如 3 能被 12 整除, 4 也能被 12 整除
所以我们在用试除法判断质数的时候, 就没有必要循环 d : 2~n, 只要 d : 2~n/d即可
模板题 866. 试除法判定质数 - AcWing 题库
#include<iostream> #include<cstdio> using namespace std; const int N=100+10; int n; int a[N]; bool is_prime(int x){ if(x<2){ return false; } //写成i<=x/i可以防止爆int for(int i=2;i<=x/i;i++){ if(x%i==0){ return false; } } return true; } int main(){ cin>>n; for(int i=0;i<n;i++){ scanf("%d", &a[i]); } for(int i=0;i<n;i++){ if(is_prime(a[i])){ puts("Yes"); } else{ puts("No"); } } return 0; }
二 筛质数 O(n)
筛法的基本思想是有一组数 2,3,4,5,6,7,8,9,10,11,12,... 顺着这组数从前往后遍历, 把遍历到的数的倍数删掉
void get_primes(){ for(int i=2;i<=n;i++){ if(!st[i]){ primes[cnt++]=i; } for(int j=i+i; j<=n; j+=i) st[j]=true; } }
这种朴素算法的时间复杂度为 n×(1/1+1/2+...+1/n)≈n⋅lnn≈O(n⋅logn)
观察这种朴素筛法我们可以发现, 遍历的过程当中,没有必要去删掉每个数的倍数, 上面的例子当中 12 就在遍历到 2, 3, 4, 6 的时候筛掉, 但是 4, 6 本身已经被筛掉了, 所以我们在遍历的过程中, 没有必要删掉每个数的倍数, 只要删掉质数的倍数既可以了
void get_primes(){ for(int i=2;i<=n;i++){ if(!st[i]){ primes[cnt++]=i; for(int j=i+i; j<=n; j+=i) st[j]=true; // 放入 if 语句当中, 只删掉质数的倍数 } } }
这种算法的时间复杂度为 n×(1/1+1/2+...+1/p)≈O(n⋅loglogn), 1/1+1/2+...+1/p大概有 n/lnn项, 这种筛法被称为埃氏筛法
如果用埃氏筛法, 上面的例子当中 12 就会在遍历到 2, 3 的时候筛掉, 这当中还是有一些重复操作, 于是就有了线性筛法
void get_primes(){ for(int i=2;i<=n;i++){ if(!st[i]){ primes[cnt++]=i; } // 把所有的 primes[j]*i 使用其最小质因子删掉 for(int j=0;primes[j]<=n/i;j++){ st[primes[j]*i]=true; if(i%primes[j]==0) break; } } }
与埃氏筛法不同的是, 线性筛法是把所有的 primes[j]*i 筛掉, 这里 i 是一个质数, primes[j] 是在之前迭代种得到的所有比 i 小的质数
- 当
i%primes[j]==0时, 说明primes[j]是i的最小质因子 (primes[j]是递增的), 因此primes[j]一定是primes[j]*i的最小质因子 - 当
i%primes[j]!=0时, 说明primes[j]一定小于i的所有质因子, 所以primes[j]也一定是prime[j]*i的最小质因子
综上两条, primes[j]*i 是被它的最小质因子 primes[j] 筛掉的, 但是当 i%primes[j]==0, 必须 break, 因为 primes[j] 是 i 的最小质因子, 所以 primes[j+1]*i 的最小质因子是 primes[j], 而不是 primes[j+1], primes[j+1]*i 不是被它的最小质因子筛掉的
对于一个合数 x, 假设 primes[j] 是 x 的最小质因子, 当 i 枚举到 x/primes[j] 时, i 枚举到 x 之前一定会先到达 x/primes[j] 所以这个 x 就被筛掉了, 而且仅仅只是被最小质因子筛掉了一次
所有合数都只会被它的最小质因子筛掉一次, 算法复杂度为 O(n)
模板题 868. 筛质数 - AcWing 题库
#include<iostream> #include<cstdio> using namespace std; const int N=1e6+10; int n; int primes[N], cnt; bool st[N]; void get_prime(){ for(int i=2;i<=n;i++){ // 这个数没有被筛掉,说明它是一个质数,就把它存起来 if(!st[i]){ primes[cnt++]=i; } // 把所有的 i*primes[j] 使用其最小质因子删掉 for(int j=0;primes[j]<=n/i;j++){ st[i*primes[j]]=true; if(i%primes[j]==0){ break; } } } } int main(){ cin>>n; get_prime(); cout<<cnt<<endl; return 0; }
