Description
redraiment在家极度无聊，于是找了张纸开始统计素数的个数。
设函数f(n)返回从1->n之间素数的个数。
redraiment发现:
f(1) = 0
f(10) = 4
f(100) = 25
...
满足g(m) = 17 * m 2 / 3 - 22 * m / 3 + 5 / 3
其中m为n的位数。
他很激动，是不是自己发现了素数分布的规律了！
请你设计一个程序，求出1->n范围内素数的个数，来验证redraiment是不是正确的，也许还可以得诺贝尔奖呢。^_^
Input
输入包括多组数据。
每组数据仅有一个整数n (1≤n≤10,000,000)。
输入以０结束
Output
对于每组数据输入，输出一行，为1->n(包括n)之间的素数的个数
Sample Input
Sample Output
0 4 18 25 思路： 筛选法求素数 上面题干全废话... 参考代码：
#include<stdio.h> #include<math.h> int a[10000007]; int main() { int i,j,sum,n; a[1]=0; a[2]=1; while(scanf("%d",&n)!=EOF&&n) { if(n==1) { printf("0n"); continue; } else if(n==2) { printf("1n"); continue; } sum=1; for(i=3;i<=n;i+=2)//i+=2配上a[i]直接忽略偶数 { for(j=3;j<=i&&i*j<=n;j+=2) a[i*j]=1;//因为可以分解成i*j说明肯定不是素数 排除 if(a[i]!=1) sum++; } printf("%dn",sum); } return 0; }
