数论——质数筛法

小灰灰 2021-11-10 02:04 410阅读 0赞

**一、埃拉托斯特尼（Eratosthenes）筛法**

算法思想：

要得到自然数n以内的全部素数，必须把不大于![5ab5c9ea15ce36d3884f4f0b39f33a87e950b146.jpg][] 的所有素数的倍数剔除，剩下的就是素数。给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。

模板题链接：[筛质数][Link 1]

代码实现：时间复杂度O(nloglogn)

1 #include <iostream>
     2 #include <algorithm>
     3 #include <cstring>
     4 #include <cstdio>
     5 const int N = 10000000+10;
     6 int p[N];
     7 
     8 void prime(int n)
     9 {
    10     p[1]=1;
    11     for(int i=2;i<=n;i++)
    12     {
    13         if(p[i])continue;
    14         for(int j=2;j<=n/i;j++)p[i*j]=1;
    15     }
    16 }
    17 
    18 int main()
    19 {
    20     int n;scanf("%d",&n);
    21     prime(n);
    22     int ans=0;
    23     for(int i=1;i<=n;i++)
    24         if(!p[i])ans++;
    25     printf("%d\n",ans);
    26     return 0;
    27 }

**二、欧拉（Euler）筛法**

欧拉筛法弥补了埃氏筛法会重复筛去合数的缺陷，而保证了**每个合数只会被其最小质因子筛去且只会被筛去一次**，在筛出质数的同时还得出了每个数的最小质因子，一举两得，是数论中非常常用也非常重要的一个算法。

先上代码：时间复杂度O(n)

1 #include <iostream>
     2 #include <algorithm>
     3 #include <cstring>
     4 #include <cstdio>
     5 const int N = 10000000+10;
     6 
     7 int primes[N],cnt;
     8 int vis[N];
     9 
    10 void Euler_prime(int n)
    11 {
    12     for(int i=2;i<=n;i++)
    13     {
    14         if(!vis[i])primes[++cnt]=i;
    15         for(int j=1;primes[j]<=n/i;j++)
    16         {
    17             vis[primes[j]*i]=1;
    18             if(i%primes[j]==0)break;
    19         }
    20     }
    21 }
    22 
    23 int main()
    24 {
    25     int n;scanf("%d",&n);
    26     Euler_prime(n);
    27 
    28     printf("%d\n",cnt);
    29     return 0;
    30 }

算法理解：

上述第18行代码保证了primes\[j\]一定小于等于i的所有质因子（因为如果primes\[j\]枚举到i的某个质因子时便会跳出枚举的循环），故primes\[j\]是primes\[j\]\*i的最小质因子。

下面证明：**所有合数只会被其最小质因子筛去，且只会被筛一次。**

**　　**对于任意一个合数k，可以表示成k=p\*(k/p)，p是k的最小质因子。由于p≤(k/p)的所有质因子(k/p就相当于上述代码中的i)，所以只有当i枚举到k/p时k才会被筛去，而枚举到其他任何数皆不会筛去k。

转载于:https://www.cnblogs.com/ninedream/p/11210339.html

[5ab5c9ea15ce36d3884f4f0b39f33a87e950b146.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D21/sign=25860e3dacc3793179688128ebc45133/5ab5c9ea15ce36d3884f4f0b39f33a87e950b146.jpg
[Link 1]: https://www.acwing.com/problem/content/870/