题目要求：打印出1-20亿之间的所有素数 C言语实现。
如果动态申请内存就要考虑你机子的内存是不是够了。
当然在内存允许的情况下越快越好 真不希望看个黑屏看半小时。。。
给代码 大家一起来测速（能运行就只比速度） 前三名给分 60 30 10 呵呵。

20亿太大了啊  
我电脑把奇数空跑一圈（10亿） 还需要接近3秒呢

kk

这个确实头有点大了

开20个线程，一个线程算1亿
时间是不是能缩短20倍啊

大点好啊 逼人想办法
如果都觉得大 那么缩小到5亿怎么样啊。

特来学习！

直接用筛选法，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 编辑 ]

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 编辑 ]

用笔来计算一个超大数是否是素数的话  是不是要累死啊