PAT（乙级）1013

1013. 数素数 (20)

令Pi表示第i个素数。现任给两个正整数M <= N<=10^4，请输出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

分析：没有什么好办法，只好把第1个到10000个素数给求出来。

代码如下：

#include <stdio.h>
#include <math.h>
int fun(int a);
int main(void)
{
	int m,n;
	scanf("%d %d",&m,&n);
	int i,j = 1,k;
	int flag = 1;
	int num[10001];
	for(i = 2;j < 10001; i++)
	{
		k = fun(i);
		if(0 == k)
		{
			num[j++] = i;
		}
	}
	for(i = m; i < n; i++)
	{
		if(0 == flag % 10)
		{
			printf("%d
",num[i]);
		}
		else
		{
			printf("%d ",num[i]);
		}
		flag++;
	}
	printf("%d",num[n]);

	return 0;
}

int fun(int a)
{
	int flag = 0;
	int j;
	for(j = 2; j <= sqrt(a); j++)
	{
		if(0 == a%j)
		{
			flag = 1;
			break;
		}
	}
	return flag;
}