素数表

题目：令Pi表示第i个素数。现任给两个正整数M <= N <= 104，请输出PM到PN的所有素数。
方法：制作出素数表，素数表可以不必用2_{sqrt(N),只需利用2}sqrt(N)之间的素数来除即可；减少了试除次数，降低了时间复杂度；
代码：
#include<stdio.h>
#include<math.h>
#define N 10000
int prime[N];
void MakePrime()
{
int n=23,sqrtn,i=8,j,m;
prime[0]=2;prime[1]=3;prime[2]=5;prime[3]=7;prime[4]=11;prime[5]=13;prime[6]=17;prime[7]=19;
while(i<N)
{
j=0;sqrtn=sqrt(n);
while(prime[j]<=sqrtn)
{
if(n%prime[j]==0) break;
j++;
}
if(prime[j]>sqrtn)
{
prime[i]=n;
i++;
}
n+=2;
}
}
int main()
{
MakePrime();
int n,m,count=0;
scanf("%d%d",&n,&m);
for(int i=n-1;i<m;i++)
{
count++;
if(count%10==0) printf(" %d\n",prime[i]);
else if(count%10==1) printf("%d",prime[i]);
else printf(" %d",prime[i]);
}
}