UVA 10200 Prime Time

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1141

这题居然暴力过了，我能说啥？我能说啥？

哎……下回一定要学会先算时间复杂度……

直接暴力过去，就是非常简单的一道题。先把素数打个表，然后再打个表表示0~n范围内的素数数目。然后完事。

#include<stdio.h> #include<math.h> #include<string.h> int num[10000+10],rank[10000+10]; int Judge(int x) { for(int i=2;i<=sqrt(x);i++) { if(x%i==0) return 0; } return 1; } void _prime() { int i; for(i=0;i<=39;i++) num[i]=1; for(i=40;i<=10000;i++) num[i]=Judge(i*i+i+41); } int main() { int i,a,b; _prime(); rank[0]=1; for(i=1;i<=10000;i++) { if(num[i]) rank[i]=rank[i-1]+1; else rank[i]=rank[i-1]; } while(~scanf("%d%d",&a,&b)) { int sum=b-a+1; int c=rank[b]-rank[a]; if(num[a]) c++; printf("%.2lf\n",1.0*c/sum*100+1e-6); } return 0; }