PAT-B-1013-数素数

令 P**i 表示第 i 个素数。现任给两个正整数 M≤N≤104，请输出 P**M 到 P**N 的所有素数。

输入格式：

输入在一行中给出 M 和 N，其间以空格分隔。

输出格式：

输出从 P**M 到 P**N 的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。

输入样例：

5 27

输出样例：

1
2
3

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

Code

#include <iostream>
using namespace std;

//尽量大
const int maxn=1000001;
int prime[maxn],pnum=0;
bool p[maxn]={0};

void getPrime(int count){
    //记住素数表都是小于最大值
    for(int i=2;i<maxn;i++){
        //为false则此数是素数
        if(p[i]==false){
            prime[pnum++]=i;
            if(pnum==count)return;
            for(int j=2*i;j<maxn;j+=i){
                p[j]=true;
            }
        }
    }
}

int main(){
	
	int m,n,count=0;
	scanf("%d%d",&m,&n);
    getPrime(n);

    for(int i=m-1;i<n;i++ ){
        count++;
        //每行第一个只输出素数
		if (count % 10 == 1) 
			printf("%d", prime[i]);
		else
			printf(" %d", prime[i]);
		
        //没十个输出一个空格
		if (count % 10 == 0)
			printf("\n");
    }
	return 0;
}