编程量*① 难度* 性能要求** (1秒)
聪聪在研究素数, 可是为搞清一些素数究竟在素数集合中排名老几, 伤透了脑筋 。 还是你帮他编个程序搞定吧, 否则, 他慢腾腾慢腾腾地数, 数到什么时候去?!
聪聪把素数放在一个叫 prime.txt 的文件中,里面大概有上千个正整数,每个正整数N(1≤N≤1000000)占1行。运行结果也是每个数占1行,不过,结果中的每个数实际上是输入的正整数在素数集合中的排名, 如果输入的不是素数(这太有可能了)那就输出一个0来表示。
样本输入文件的内容和输出结果示例于下:
//=================================== //EX0601_1.cpp //素数的排位(二分搜索版） //=================================== #include<stdlib.h> #include<stdio.h> //----------------------------------- const int nPrime = 78498; int p[nPrime] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61}; //----------------------------------- bool isPrime(int n){ for(int j=1; p[j]*p[j]<=n; j++) if(n%p[j] ==0) return false; return true; }//----------------------------------- int comp(const void* p1,const void* p2){ return *(int*)p1 - *(int*)p2; }//---------------------------------- int main(){ for(int i=67,m=18; i<1000000; i+=2) if(isPrime(i)) p[m++]=i; freopen("prime.txt","r",stdin); for (int a, *ptr; scanf("%d ", &a) ! =EOF ){ ptr = (int*)bsearch(&a, p, nPrime, sizeof(int), comp); printf("%d\n", (ptr ? ptr-p+1 : 0)); } }//==================================//=================================== //EX0601_2.cpp //素数的排位（向量版） //=================================== #include<fstream> #include<iostream> #include<vector> using namespace std; //----------------------------------- int main() { vector<int> p(1000001,1); for(int i=2; i<=997; ++i) if(p[i]) for(int j=i*i; j<=1000000; j+=i) p[j]=0 for(int i=2,j=1; i<1000001; ++i) if(p[i]) p[i]=j++; ifstream cin("prime.txt"); for(int a; cin>>a; ) cout<<p[a]<<"\n"; }//==================================数组版：
/=================================== //EX0601_3.cpp //素数的排位（数组版） //=================================== #include<stdio.h> //----------------------------------- int p[1000001]; int main() { for(int i=2; i<=997; ++i) if(!p[i]) for(int j=i*i; j<=1000000; j+=i) p[j]=1 for(int i=2,j=1; i<1000001; ++i) p[i] = (p[i]?0:j++); freopen("prime.txt","r",stdin); for(int a; scanf("%d ",&a) !=EOF; ) printf("%d\n",p[a]); }//==================================