已知素数序列为 2、3、5、7、11、13、17、19、23、29……，即素数的第一个是 2，第二个 是 3，第三个是 5……那么，随便挑一个数，若是素数，能确定是第几个素数吗？如果不是 素数，则输出 0。 输入格式: 测试数据有多组，处理到文件尾。每组测试输入一正整数 N（1≤N≤1000000）。 输出格式: 对于每组测试，输出占一行，如果输入的正整数是素数，则输出其排位，否则输出 0。
输入样例:
2
6
4
5
13
991703
输出样例:
1
0
0
3
6
77901
#include <stdio.h> #include <math.h> int prime(int x)//求素数函数，素数返回 1，否则返回 0 { int i; for(i=2;i<=sqrt(x);i++) if (x%i==0) return(0); return(1); } int main(void) { int n,i,s; while((scanf("%d",&n))!=EOF) { s=0; if(prime(n)==0) printf("%d\n",s); else { for (i=1;i<=n;i=i+2) if(prime(i)==1) s++; printf("%d\n",s); } } return 0; }
/*埃氏 Eratosthenes 筛选法（求一个范围中的所有素数） 我们用一个标记数组 f[maxi]，其中 f[i]=0 为素数，否则为非素数，首先我们知道 1，和 0 都不是素数，所以 f[0]=1,f[1]=1 1.随后我们在未标记的数里面找最小的数，为 2，他不是任何数的的倍数，所以 2 是素数， 此时我们就把所有 2 的倍数都标记为 0；3，6，8，10……2*i 2.我们再从剩余未标记的数里面找最小的数，为 3，他也不是任何数的倍数，所以 3 是素数， 此时我们把所有 3 的倍数也都标记为 0；6，9，12，15，18……3*i 3.我们再从所有未标记的数里面找最小的数，为 5，他也不是任何数的素数，所以 5 是素数， 此时我们把所有 5 的倍数都标记为 0；10，15，20，25……5*i, …………以此类推 从 2 开始寻找素数，每次找到一个素数后就将它的倍数全部筛掉，不断循环，直至原队列 （数组）为空。 时间复杂度为 O(nlog logn)。*/
#include <stdio.h> int main() { int n,len=0,i=0,k=0,a[1000]={0},b[1000]; // st[x]存储 x 是否被筛掉 while((scanf("%d",&n))!=EOF) { b[len++]=n;} for (k=0;k<len;k++) { if (b[k]==2) { a[k]=1;continue;}//偶数 2 是素数 if (b[k]%2==0){ a[k]=0;continue;}//偶数肯定不是素数 int st[1000000]={1,1,0}; for(i=2;i<=b[k];i=i+1) { if(!st[i]) { a[k]++; for(int j=2 * i; j<=b[k]; j=j+i) {st[j]=1;} } } } for (k=0;k<len-1;k++) { printf("%d\n",a[k]); } printf("%d",a[k]); return 0; }
