// 准筛法求一万亿以内素数（VC 6.0）
// 耗时13137.3秒(Dell机)
#include <stdio.h>
#include <time.h>  //用于统计时间的头文件
#include <stdlib.h>
#include <memory.h>

#define PMAX 1000000000000
#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;
}

一万亿以内有37607912018个素数，最后1000个连续数中有38个素数，它们是
999999999091    999999999101    999999999133    999999999143    999999999161    999999999247
999999999253    999999999269    999999999277    999999999287    999999999293    999999999301
999999999331    999999999359    999999999391    999999999457    999999999497    999999999517   
999999999529    999999999571    999999999577    999999999589    999999999599    999999999611   
999999999617    999999999673    999999999697    999999999707    999999999767    999999999847   
999999999857    999999999863    999999999877    999999999899    999999999937    999999999959   
999999999961    999999999989   



[ 本帖最后由 yu_hua 于 2010-12-18 20:04 编辑 ]

呵呵。做学问忌讳什么？忌讳“浅尝辄止”。
写代码就要写 算法上最好的、速度上最快的、内存上最省的 代码。
求素数就追求尽可能大的素数，挑战人脑与电脑的极限！

请你看 1 楼 绿色的文字