PAT1013 数素数

1013 数素数 (20分)

令

输入格式：

输入在一行中给出

输出格式：

输出从

输入样例：

5 27

输出样例：

11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103


思路：采用“埃氏”筛法
记忆：1000000（10^6）之内有78498个素数，10000000（10^7）之内有664579个素数

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 
 5 using namespace std ;
 6 
 7 const int N = 10000010 ;
 8 
 9 bool st[N] ;
10 int primes[N] ;
11 int n, m ; 
12  
13  
14 int main(){
15     cin >> n >> m ;
16     
17     int idx = 0 ;
18     
19     for(int i=2;i<10000010;i++){
20         if(!st[i]){
21             primes[idx++] = i ;
22             if(idx == m){
23                 break ;
24             }
25             for(int j=i;j<=10000010;j += i){
26                 st[j] = true ;
27             }
28         }
29     }
30     idx = 0 ;
31     for(int i=n-1;i<m;i++){
32         idx ++ ;
33         if(idx==10 || i==m-1){
34             printf("%d
",primes[i]) ;
35             idx = 0 ;
36         }else{
37             printf("%d ",primes[i]) ;
38         }
39     }
40     
41     return 0 ;    
42 }