| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1516 人关注过本帖, 1 人收藏
标题:尝试列出 2,000,000以下的所有素数
只看楼主 加入收藏
voidx
Rank: 12Rank: 12Rank: 12
来 自:邯郸
等 级:火箭侠
帖 子:1250
专家分:3538
注 册:2011-4-7
结帖率:77.78%
收藏(1)
已结贴  问题点数:20 回复次数:23 
尝试列出 2,000,000以下的所有素数
如题,请大家尝试一下,然后把自己的算法和程序运行时间贴出来
搜索更多相关主题的帖子: 时间 
2011-04-10 18:43
水晰
Rank: 3Rank: 3
来 自:新疆
等 级:论坛游侠
帖 子:39
专家分:113
注 册:2011-4-6
收藏
得分:0 
#include <stdio.h>
void main()
{
 int i,k;
 printf("%d",1);
 for(i=3;i<2000000;i++)
 {
  for(k=2;k<i;k++)
  {
      if(i%k==0) break;
  if(k+1==i) printf(" %d",i);
      }
 }
printf("\n");
}
      

        
2011-04-10 19:02
张敏樱木花道
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:139
专家分:137
注 册:2011-3-26
收藏
得分:0 
回复 2楼 水晰
我觉得可能你的算法有点问题,int型的变量装不下200000那么大的数的,会出错的……
2011-04-10 19:39
张敏樱木花道
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:139
专家分:137
注 册:2011-3-26
收藏
得分:0 
我试了一下,将int改为long可以得出答案。
2011-04-10 19:52
voidx
Rank: 12Rank: 12Rank: 12
来 自:邯郸
等 级:火箭侠
帖 子:1250
专家分:3538
注 册:2011-4-7
收藏
得分:0 
请贴出你的程序运行时间
2011-04-10 20:58
水晰
Rank: 3Rank: 3
来 自:新疆
等 级:论坛游侠
帖 子:39
专家分:113
注 册:2011-4-6
收藏
得分:0 
只是试了试比较小的数. 看来经验不够啊.
2011-04-10 21:06
voidx
Rank: 12Rank: 12Rank: 12
来 自:邯郸
等 级:火箭侠
帖 子:1250
专家分:3538
注 册:2011-4-7
收藏
得分:0 
回复 6楼 水晰
你试试看2,000,000你的算法会让你等到失去耐性。
我可以告诉你算法设计够好的话可以在 2 秒内得到结果(不算printf()的时间)
2011-04-10 21:10
ansic
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:恍惚窈冥
等 级:城市猎人
帖 子:1543
专家分:5367
注 册:2011-2-15
收藏
得分:0 
麻烦楼主自行测试吧。我绝对相信楼主可以在2秒以内得出所有质数的能力, 可惜, 我是菜鸟,
程序代码:
root@~ #cat isp.c
#include <stdio.h>
#include <stdbool.h>

int main (void) {

        bool isp (int num);
        long int i;
        for(i=2;i<2000000;i++) {
                if(isp(i)==true) printf ("%li\n",i);
        }
        return 0;

}
bool isp (int num) {
        bool result=true;
        long int i;
        for (i=num-1;i>1;i--) {
                if (num%i==0) {
                        result=false;
                        break;
                }
        }
        return result;
}
root@~ #


[ 本帖最后由 ansic 于 2011-4-10 21:46 编辑 ]

善人者,不善人之师;不善人者,善人之资。不贵其师,不爱其资,虽智大迷。
2011-04-10 21:43
kwxx
Rank: 8Rank: 8
等 级:蝙蝠侠
帖 子:309
专家分:913
注 册:2009-5-11
收藏
得分:0 
想用筛法,下标达不到范围,不知怎么解决,用链表恐怕会很慢吧。只求出了 200000 以下的素数,差了一个数量级。
//筛法求素数

#include<stdio.h>
#include<math.h>
#define N 200000/2  
void main()
{
    long i,j,k,n=0,a[N]={2,3};
   
    for(i=2;i<N;i++)a[i]=a[i-1]+2;                    //将5--N中所有数放入数组(偶数没放)

    k=sqrt(N);                                //逐步去掉 3的倍数、。。。等等  -- 筛法  i 是"筛"
    for(i=1;i<k;i++)
        for(j=i+1;j<N;j++)
            if(a[i]!=0 && a[j]!=0)
                if(a[j]%a[i]==0)a[j]=0;
   
    for(i=0;i<N;i++)    //输出所有素数
        if(a[i]!=0 )
        {
            n++; printf("%8ld",a[i]);
            if(n%10==0)printf("\n");
        }

    printf("\nn=%ld\n",n);
}
2011-04-10 22:52
voidx
Rank: 12Rank: 12Rank: 12
来 自:邯郸
等 级:火箭侠
帖 子:1250
专家分:3538
注 册:2011-4-7
收藏
得分:0 
其实用 sieve 完全可以的。如果注释掉 printf(), msys 测得时间也只有 100ms 左右

程序代码:
#include <stdio.h>

#define LMT 2000000

int main() {
    char m[LMT] = {0};
    int i, j;
    printf ("2\t");
    for (i = 3; i < LMT; i+= 2) {
        if (!m[i]) {
            printf("%d\t", i);
            for (j = i * 3; j < LMT; j += i * 2) {
                m[j] = 1;
            }
        }
    }
    return 0;
}


[ 本帖最后由 voidx 于 2011-4-10 23:27 编辑 ]
2011-04-10 23:18
快速回复:尝试列出 2,000,000以下的所有素数
数据加载中...
 
   



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

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