数素数(PAT)

1.题目描述

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

2.输入描述:

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

3.输出描述:

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

4.输入例子:

5 27

5.输出例子:

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

6.解题思路：

1.输入M，N，创建一个整形动态数组，为其分配（N-M+1）大小的内存空间，用于保存M~N范围内的素数；
2.循环判断素数，用k=0代表非素数，k=1代表素数；
3.每确定一个素数用 l 计数一次，即确定该素数是第几个素数，当M<= l <=N时，将该范围内的素数存入数组中；
4.遍历数组输出，初始化k=0，并用k计数输出的个数，当k能被十整除时输出’\n’换行继续输出

7.源代码：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main()
{
	int M,N,i=2,j,l=1,k,*p;
	scanf("%d%d",&M,&N);
	p=(int*)malloc((N-M+1)*(sizeof(int)));
	do
	{
		k=1;
		for(j=2;j<=sqrt(i);j++)
		{
			if(i%j==0)
				k=0;
		}
		if(k==1)
		{	
			if(l>=M&&l<=N)
				p[l-M]=i;
			l++;
		}
		i++;
	}while(l<=N);
	k=0;
	for(i=0;i<N-M;i++)
	{
		printf("%d ",p[i]);
		k++;
		if(k%10==0)
			printf("\n");
	}
	printf("%d",p[N-M]);
	return 0;
}