一般数筛到欧拉筛

佚名 6年前 (2019-04-16) 随笔 683人围观抢沙发百度已收录

数筛用来确定素数

初始想法

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int prime[40004],num[40004];
 4 void isprime()
 5 {
 6     int c=0;
 7     for(int i=2;i<=40004;i++)
 8     {
 9         if(!num[i])
10          {
11              prime[c++]=i;
12              for(int j=i;j<=40004;j+=i)
13              {
14                  num[j]=1;
15              }
16          }
17     }
18 }
19 int main()
20 {
21     isprime();
22     for(int i=1;i<=400;i++)
23         printf("%d\n",prime[i]);
24 }

欧拉筛：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int t,prime[40005],num[40005];
 4 void isprime()
 5 {
 6     int c=0;
 7     for(int i=1; i<=40000; i++)
 8         num[i]=1;
 9     for(int i=2; i<=40000; i++)
10     {
11         if(num[i]==1)
12             prime[c++]=i;
13         for(int j=0; j<c&&prime[j]*i<40000; j++)
14         {
15             num[prime[j]*i]=0;
16             if(i%prime[j]==0)
17                 break;
18         }
19     }
20 }
21 int main()
22 {
23     isprime();
24     for(int i=1;i<=400;i++)
25         printf("%d\n",prime[i]);
26 }