【数论】筛法求素数 （ACM基础知识）

当只需要求某个数是不是素数的时候，我们可以直接通过素数的定义来求，即如果可以被除1及素数本身的其他数整除，则这个数不是素数

但是如果要求某个范围内的素数的个数的时候这个方法就不太合适了。虽然我们可以进行预处理，但是这种方法比较慢，一旦范围过大，预处理过程便会超时。

因此，需要使用筛法求素数，这样可以在线性时间内求得范围内每个数是否为素数。

思想：去除要求范围内所有的合数，剩下的就是素数，而任何合数都可以表示为素数的乘积，因此，如果已知一个数为素数，则它的倍数都是合数

普通的线性筛法：

1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define ll long long
 6 const int MAX = 1000100;   // 求MAX范围内的素数
 7 ll su[MAX],cnt;
 8 bool isprimer[MAX];
 9 void prime()
10 {
11     cnt = 1;
12     memset(isprimer,1,sizeof isprimer);   // 初始化认为所有数都为素数
13     isprimer[0] = isprimer[1] = 0;   // 0和1不是素数
14     for(ll i = 2;i <= MAX;i++)
15     {
16         if(isprimer[i])   // 保存素数
17         {
18             su[cnt++] = i;
19         }
20         for(ll j = i*2;j <= MAX;j += i)   // 素数的倍数都为合数
21         {
22             isprimer[j] = 0;
23         }
24     }
25 }
26 
27 int main()
28 {
29     prime();
30     for(ll i = 1;i < cnt;i++)
31         printf("%lld ",su[i]);
32     return 0;
33 }

弊端：虽然这种方法已经极大的减小了判断的时间，但是仍然有一些重复计算。比如判断2的时候将（2*3）6筛了一遍。

在判断3的时候又将6(3*2)筛了一遍。

如果只筛选小于等于i的素数与i的乘积，便可以尽量减少重复的筛选，也不会遗漏掉，大大提高了计算效率

优化后的线性筛法：

1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define ll long long
 6 const int MAX = 1000100;   // 求MAX范围内的素数
 7 ll su[MAX],cnt;
 8 bool isprimer[MAX];
 9 void prime()
10 {
11     cnt = 1;
12     memset(isprimer,1,sizeof isprimer);   // 初始化认为所有数都为素数
13     isprimer[0] = isprimer[1] = 0;   // 0和1不是素数
14     for(ll i = 2;i <= MAX;i++)
15     {
16         if(isprimer[i])   // 保存素数
17         {
18             su[cnt++] = i;
19         }
20         for(ll j = 1;j < cnt && su[j]*i < MAX;++j)   // 素数的倍数都为合数
21         {
22             isprimer[su[j]*i] = 0;   // 筛掉小于等于i的素数和i的积构成的合数
23         }
24     }
25 }
26 
27 int main()
28 {
29     prime();
30     for(ll i = 1;i < cnt;i++)
31         printf("%lld ",su[i]);
32     return 0;
33 }

原文链接: https://www.cnblogs.com/duny31030/p/8977646.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍