pat乙级1013

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

输入格式：

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

输出格式：

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

输入样例：

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
	

	

		代码如下：
	

	

		
#include<iostream>
#include<cmath>
using namespace std;
#define N 104731//偷个小懒，第1W个素数为104729，嘿嘿嘿
int a[N];
int prime[10000];
int psize=0;
void init()//经典的素数筛选法
{
	for (int i = 0; i < N; i++)
		a[i] = 1;
}
void getprime()
{
	init();
	int k = (int)sqrt(N);
	for (int i = 2; i < N; i++)
	{
		if (a[i] == 0)continue;
		prime[psize++] = i;
		if (i > k)
			continue;
		for (int j = i * i; j < N; j += i)
			a[j] = 0;
	}
}
int main()
{
	int n, m;
	getprime();
	while (cin >> n >> m)
	{
		int cnt = 0;
		for (int i = n - 1; i < m ; i++)
		{
			cnt++;//10个一行
			if (cnt == 10)
			{
				cout << prime[i] << endl;
				cnt = 0;
			}
			else
			{
				if (i == m - 1)//注意最后一个如果不是一行的第10个，它的后面也没有空格
					cout << prime[i] << endl;
				else
					cout << prime[i] << " ";
			}
		}
	}
	return 0;
}