| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 5987 人关注过本帖
标题:【新手求助】大范围(1e9内)求素数问题
只看楼主 加入收藏
雨铃半百
Rank: 1
来 自:223-3
等 级:新手上路
帖 子:14
专家分:0
注 册:2017-10-8
结帖率:100%
收藏
已结贴  问题点数:10 回复次数:4 
【新手求助】大范围(1e9内)求素数问题
题目:输入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;
}
搜索更多相关主题的帖子: 范围 素数 int return num 
2017-10-08 17:00
雨铃半百
Rank: 1
来 自:223-3
等 级:新手上路
帖 子:14
专家分:0
注 册:2017-10-8
收藏
得分: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-08 17:01
pydlq
Rank: 6Rank: 6
等 级:侠之大者
威 望:1
帖 子:129
专家分:488
注 册:2017-9-5
收藏
得分:0 
看错了...

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

2017-10-08 17:45
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:10 
https://bbs.bccn.net/viewthread.php?tid=475824&extra=&page=1

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

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-10-08 18:11
雨铃半百
Rank: 1
来 自:223-3
等 级:新手上路
帖 子:14
专家分:0
注 册:2017-10-8
收藏
得分:0 
回复 4楼 九转星河
哇 谢谢谢谢,帮大忙了~
因为还是新手,刚注册的论坛,也不大会用,这个很有用,十分感谢。
2017-10-09 00:42
快速回复:【新手求助】大范围(1e9内)求素数问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.607826 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved