超大素数查找
第一亿的素超大素数查找
第一亿的素数在一分钟内找出；是第100000000素数
#include <stdio.h>
#include <time.h>  //用于统计时间的头文件
#include <stdlib.h>
#include <memory.h>

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