pat_basic_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

解题思路：

我先把前20个素数直接列出来，如果没有被这些已知素数覆盖到，那就找到了。

#include <stdio.h>
#define MAXN 10240
 
int main()
{
	int M, N, j, t;
	long int i;
	if ( scanf("%d %d", &M, &N)==EOF ) printf("error\n");
	long int Prime[MAXN] = {
		2, 3, 5, 7, 11,13,17,19,23,29,
		31,37,41,43,47,53,59,61,67,71,
	};
	
	for ( i=73, j=20; j<N; i+=2 ) {
		for ( t=1; t<j && Prime[t]*Prime[t]<i; t++ ) {
			if ( i%Prime[t]==0 ) break;
		}
		if ( Prime[t]*Prime[t]>i ) {
			Prime[j] = i;
			j ++;
		}
	}
	
	for ( j=M-1, t=1; j<N; j++, t++ ) {
		if ( j!=N-1 ) {
			t%10==0 ? printf("%ld\n", Prime[j]) : printf("%ld ", Prime[j]) ;
		} else {
			printf("%ld\n", Prime[j]);
		}
	}
	
	return 0;
}