素数筛法

一、素数

素数筛选，判断<MAXN的数是不是素数，模板by kuangbin

 1 //判断小于MAXN的数是否是素数
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <cstring>
 6 using namespace std;
 7 const int MAXN=1e5+5;
 8 bool notprime[MAXN];            //表，false是素数，true不是素数
 9 void isprimer(){
10     memset(notprime,false,sizeof(notprime));
11     notprime[0]=notprime[1]=true;
12     for(int i=2;i<MAXN;i++){
13         if(!notprime[i]){
14             if(i>MAXN/i)    continue;       //防止后面i*i溢出（或者i,j用Long long）
15             //直接从i*i开始就可以，小于i倍的已经筛过了，注意是j+=i;
16             for(int j=i*i;j<MAXN;j+=i){
17                 notprime[j]=true;
18             }
19         }
20     }
21 }
22 int main(){
23     int n;
24     isprimer();
25     cin>>n;
26     for(int i=0;i<n;i++){
27         if(notprime[i]==false)
28             cout<<i<<" ";
29     }
30     return 0;
31 }

二、PAT乙级：1013 数素数

 1 /*
 2 令 Pi表示第 i 个素数。现任给两个正整数 M≤N≤10^4,请输出 PM到 PN的所有素数。
 3 
 4 输入格式：
 5 输入在一行中给出 M 和 N，其间以空格分隔。
 6 
 7 输出格式：
 8 输出从 PM到 PN的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。
 9 
10 输入样例：
11 5 27
12 
13 输出样例：
14 11 13 17 19 23 29 31 37 41 43
15 47 53 59 61 67 71 73 79 83 89
16 97 101 103
17 */
18 #include <iostream>
19 #include <cstring>
20 #include <cstdlib>
21 #include <cstdio>
22 using namespace std;
23 const int MAXN=1e7+10;
24 int primer[MAXN],num=0;
25 bool notPrimer[MAXN];
26 void isPrimer(){
27     memset(notPrimer,false,sizeof(notPrimer));
28     notPrimer[0]=notPrimer[1]=true;
29     for(int i=2;i<MAXN;i++){
30         if(!notPrimer[i]){
31             primer[num++]=i;
32             if(i>MAXN/i)    continue;
33             for(int j=i*i;j<MAXN;j+=i)
34                 notPrimer[j]=true;
35         }
36     }
37 }
38 int main(){
39     int n,m,ans=0;
40     isPrimer();
41     cin>>m>>n;
42     for(int i=m;i<=n;i++){
43         cout<<primer[i-1];
44         ans++;
45         if(ans%10!=0 &&i<n)
46             cout<<" ";  
47         else{
48             cout<<endl;
49         }                    
50     }
51     return 0;
52 }