| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2595 人关注过本帖
标题:一起来求素数
只看楼主 加入收藏
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
结帖率:99.34%
收藏
已结贴  问题点数:100 回复次数:60 
一起来求素数
题目要求:打印出1-20亿之间的所有素数 C言语实现。
如果动态申请内存就要考虑你机子的内存是不是够了。
当然在内存允许的情况下越快越好 真不希望看个黑屏看半小时。。。
给代码 大家一起来测速(能运行就只比速度) 前三名给分 60 30 10 呵呵。
搜索更多相关主题的帖子: 内存 动态 
2012-12-02 23:48
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:贵宾
威 望:423
帖 子:13688
专家分:53332
注 册:2012-10-18
收藏
得分:0 
20亿太大了啊  
我电脑把奇数空跑一圈(10亿) 还需要接近3秒呢

DO IT YOURSELF !
2012-12-03 08:58
青春无限
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江苏
等 级:贵宾
威 望:24
帖 子:3452
专家分:19340
注 册:2012-3-31
收藏
得分:0 
kk

学 会看代码…学习写程序…学会搞开发…我的目标!呵呵是不是说大话啊!!一切皆可能
2012-12-03 09:33
一个孩子
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:5
帖 子:356
专家分:954
注 册:2012-10-1
收藏
得分:0 
这个确实头有点大了

重要的不是结果,是求一个结果的过程,哪怕千难万难,当你有想要的结果时,你已走的很远
2012-12-03 10:03
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:贵宾
威 望:423
帖 子:13688
专家分:53332
注 册:2012-10-18
收藏
得分:0 
开20个线程,一个线程算1亿
时间是不是能缩短20倍啊

DO IT YOURSELF !
2012-12-03 10:07
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
收藏
得分:0 
大点好啊 逼人想办法
如果都觉得大 那么缩小到5亿怎么样啊。

梅尚程荀
马谭杨奚







                                                       
2012-12-03 10:20
heroinearth
Rank: 10Rank: 10Rank: 10
来 自:云南曲靖
等 级:青峰侠
帖 子:430
专家分:1506
注 册:2011-10-24
收藏
得分:0 
特来学习!
2012-12-03 10:32
czz5242199
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:660
专家分:2400
注 册:2011-10-26
收藏
得分:25 
直接用筛选法,20Y的数组需要8G的内存肯定不行,由于int类型是32位的,用每一位代表一个数,这样只需要20Y/32=250MB内存即可,操作的时候用位运算计算

比如a[2]就代表了从33到64这32个数,他的二进制最后一位就是33,第一位就是64,0代表是素数,1代表是合数

然后筛选的时候只需要筛选到sqrt(max)就行了,证明:筛选m时,我们会把m*2,m*3.......m*k(m*k<=max)全部筛选掉,如果m>sqrt(max),所以k<sqrt(max),所以这些数会在之前筛选(2,k)时就被筛选掉。

程序代码:
#include <stdio.h>
#include <time.h>
#define MAX 2000000000
#define N MAX/32+1

unsigned int A[N];

int main()
{
    clock_t start,finish;
    start=clock();
    
    int i,k,n=N,max=MAX,size=sqrt(max),x,y;
    memset(A,0,sizeof(A));
    for (i=2; i<size; i++)
    if (!(A[(i-1)/32]&(1<<((i-1)%32))))
    {
                                    k=i+i;
                                    while (k<=max)
                                    {
                                          A[(k-1)/32]|=(1<<((k-1)%32));
                                          k+=i;
                                    }
    }
    
    FILE *f=fopen("prime.txt","w");
    for (i=2; i<=max; i++)
    if (!(A[(i-1)/32]&(1<<((i-1)%32)))) fprintf(f,"%d\n",i);
    fclose(f);
    
    finish=clock();
    printf("%.3lf\n",((double)finish-start)/1000);
    
    system("pause");
}

图片附件: 游客没有浏览图片的权限,请 登录注册


[ 本帖最后由 czz5242199 于 2012-12-3 10:40 编辑 ]
2012-12-03 10:36
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:贵宾
威 望:423
帖 子:13688
专家分:53332
注 册:2012-10-18
收藏
得分:20 
D:\c_source\t1\Debug>t1
1999999003      1999999013      1999999049      1999999061      1999999081
1999999087      1999999093      1999999097      1999999117      1999999121
1999999151      1999999171      1999999207      1999999219      1999999271
1999999321      1999999373      1999999423      1999999439      1999999499
1999999553      1999999559      1999999571      1999999609      1999999613
1999999621      1999999643      1999999649      1999999657      1999999747
1999999763      1999999777      1999999811      1999999817      1999999829
1999999853      1999999861      1999999871      1999999873      1999999913
1999999927      1999999943      1999999973
61.4 sec
Total: 98222287
程序代码:
// 准筛法求一万亿以内素数(VC 6.0)
// 耗时13137.3秒(Dell机)
#include <stdio.h>
#include <time.h>  //用于统计时间的头文件
#include <stdlib.h>
#include <memory.h>

#define PMAX 2000000000   //原著这里是100亿 我给改成20亿了  100亿要耗时好几个小时呢
#define NUMP 78500
long prime [NUMP]={2, 3};
long prime2[NUMP]={4, 6};

void set_Prime_table(void)
{  
    long n=5,p2=9, k,kr=1,kp=2;
    while(1)
    {  
        if(n==p2)
        {  
            kr++;
            p2=prime[kr]*prime[kr];
            continue;
        }  
        for(k=1; k<kr; k++)
        {  
            if(n % prime[k]==0)goto nadd2;
        }  
        prime[kp]=n;
        prime2[kp]=n+n;
        if(++kp==NUMP)break;
        nadd2:
        n=n+2;
    }  
    if((__int64)n*n<PMAX)abort( );
    return;
}   

int main(void)
{  
    #define BLOCK 0x8000 //VC6.0最佳值(Dell机), 在赛扬-333上0x4000为最佳
    static  char pp[BLOCK];
    __int64 BASE,np=0;
    long block,dn,k,nn,t2,t1=clock( ); //t1、t2分别记录开始和结束时间
    set_Prime_table( );
    for(np=BASE=0;BASE<PMAX;BASE+=BLOCK)
    {
        memset(pp,1,BLOCK);       //预设都是素数
        if(BASE==0)pp[0]=pp[1]=0; //0和1不是素数
        block = BLOCK;
        if(PMAX-BASE<BLOCK)block=(long)(PMAX-BASE);
        for(k=0; k<NUMP; k++)
        {  
            dn = prime [k];
            nn = prime2[k];
            while(nn<block)
            {  
                pp[nn]=0;
                nn=nn+dn;
            }
            prime2[k]=nn-BLOCK;
        }  
        for(k=0; k<block; k++)if(pp[k])
        {  
            if(BASE>=PMAX-BLOCK && k>block-1000)
            printf("%I64d\t",k+BASE);//显示最后1000个连续数中的素数
            np++;
        }
    }
    t2 = clock( );
    printf("\n%0.1f sec\nTotal: %I64d\n",(t2-t1)/1E3,np);
    return 0;
}
本论坛中搜到的 作者yu-hua



[ 本帖最后由 wp231957 于 2012-12-3 10:41 编辑 ]

DO IT YOURSELF !
2012-12-03 10:40
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:贵宾
威 望:423
帖 子:13688
专家分:53332
注 册:2012-10-18
收藏
得分:0 
用笔来计算一个超大数是否是素数的话  是不是要累死啊

DO IT YOURSELF !
2012-12-03 11:03
快速回复:一起来求素数
数据加载中...
 
   



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

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