题目：输入n，求0到n之间素数的个数
要求：在一分钟内计算出n=1e9以内的情况

问题代码1：（能求但是范围不够）
#include<stdio.h>
#include<math.h>
int f(int n)
{
    int i;
    for(i=2;i<=sqrt(n);i++)
        if(n%i==0) return 0;
    return n>1;
}
int main()
{
    int n,i,num=0;
    scanf("%d",&n);
    for(i=2;i<=n;i++)
    if(f(i)) num++;
    printf("%d",num);
    return 0;
}

问题代码2：（容斥法，百度上学到的，但是有问题，输出的数不正确）
#include<stdio.h>
 #include<string.h>
 #include<math.h>
 int flag[10006];
 int num[10000],total,now,n;
 void solve(int index,int Mul,int K){
 int i,t;
 if(K==0){
 now+=n/Mul;
 return;
 }
 for(i=index;i<total-K+1;i++){
 Mul*=num[i];
 t=now;
 if(Mul<=n){
 solve(i+1,Mul,K-1);
 }
 if(t==now)//优化剪枝（1）
 return;
 Mul/=num[i];
 }
 }
 int Judge(int x){
 int t,i;
 t=sqrt(x*1.0);
 for(i=2;i<=t;i++)
 if(n%i==0)
 return 0;
 return 1;
 }
 int main(){
 int i,j,t,Count;
 memset(flag,0,sizeof(flag));
 for(i=2;i<=10000;i++){
 if(flag[i])
 continue;
 for(j=2;j*i<=10000;j++)
 flag[i*j]=1;
 }
 while(scanf("%d",&n)==1){
 Count=0;
 if(n<=10000){
 for(i=2;i<n;i++)
 if(!flag[i])
 Count++;
 }
 else{
 t=sqrt(1.0*n);
 total=0;
 for(i=2;i<=t;i++)
 if(!flag[i])
 num[total++]=i;
 for(i=1;i<=total;i++){
 now=0;
 solve(0,1,i);
 if(now==0)//优化(2)
 break;
 if(i&1)
 Count+=now;
 else
 Count-=now;
 }
 Count-=total;
 Count=n-Count-1;
 if(Judge(n))
 Count--;
 }
 printf("%d\n",Count);
 }
 return 0;
 }

看错了...

[此贴子已经被作者于2017-10-8 17:46编辑过]

https://bbs.bccn.net/viewthread.php?tid=475824&extra=&page=1

嗯,或许这个帖子对你会有所帮助~

哇 谢谢谢谢，帮大忙了~
因为还是新手，刚注册的论坛，也不大会用，这个很有用，十分感谢。