学步园

http://acm.hdu.edu.cn/showproblem.php?pid=2136

解题思路：用筛选法，求出输入的N值最大的素数的编号

#include<stdio.h><br /> #define size 1000001</p> <p>int prime[size];</p> <p>int main()<br /> {<br /> int locate=0;<br /> int n,i,j;<br /> for(j=2;j<size;j++)<br /> prime[j]=-1;<br /> prime[1] = 0;<br /> /*筛选位置*/<br /> for(i=2; i<size; i++)<br /> {<br /> if(prime[i]==-1)<br /> {<br /> locate++;<br /> for(j=i;j<size;j+=i)<br /> prime[j]=locate;<br /> }<br /> }<br /> while(scanf("%d",&n)!=EOF)<br /> printf("%d/n",prime[n]);<br /> return 0;<br /> }</p> <p>