题目描述
redraiment在家极度无聊,于是找了张纸开始统计素数的个数。设函数f(n)返回从1->n之间素数的个数。redraiment发现: f(1) = 0 f(10) = 4 f(100) = 25 … 满足g(m) = 17 * m2 / 3 – 22 * m / 3 + 5 / 3 其中m为n的位数。他很激动,是不是自己发现了素数分布的规律了! 请你设计一个程序,求出1->n范围内素数的个数,来验证redraiment是不是正确的,也许还可以得诺贝尔奖呢。^_^
输入
输入包括多组数据。每组数据仅有一个整数n (1≤n≤100000000)。输入以0结束
输出
对于每组数据输入,输出一行,为1->n(包括n)之间的素数的个数。
样例输入
1
10
65
100
0
样例输出
0
4
18
25
参考代码
#include<stdio.h>
#include<memory.h>
int a[45];
int total(int n)
{
if(n==1||n==2)return n; else
{
if(a[n]==0)
a[n]=total(n-1)+total(n-2);
return a[n];
}
}
main()
{
int n;
int m;
memset(a,0,(sizeof(a[0]))*45);
scanf("%d",&n);
while(n)
{
m=total(n);
printf("%d",m);
printf("n");
scanf("%d",&n);
}
return 0;
}
解析
暂无