今天看到一个素数的算法,利用素数集中在6x+1/6x-1的原理
整理了一下 算法如下 打印max以下num个素数:
http://lmlf001.blog.sohu.com/
void print_prime(int max,int num)
{
if(max<5)return;
unsigned long t,m,n,p;
unsigned long x;
int i,j,a,b,k;
x=max;
int z=0;
x=x/6; //x>=5
for(t=x;t>=0,z<num;t--)
{
i=1;j=1; k=t%10;
m=6*t;
/**i,j的值 是是否进行验证的标志也是对应的6t-1和6t+1的素性标志**/
if(((k-4)==0)||((k-9)==0)||((m+1)%3==0))j=0;
/*此处是简单验证6*t-1,6*t+1 是不是素数,借以提高素数纯度**/
if(((k-6)==0)||((m-1)%3==0))i=0;
/***先通过初步判断去除末尾是5,及被3整除的数***/
for(p=1;p*6<=sqrt(m+1)+2;p++ )
{
n=p*6;
/**将6*p-1和6*p+1看作伪素数来试除*****/
k=p%10;
a=1;b=1;
/**同样此处a,b的值也是用来判断除数是否为素数提高除数的素数纯度**/
if(((k-4)==0)||((k-9)==0))a=0;
if(((k-6)==0))b=0;
if(i){
/*如果i非零就对m-1即所谓6*t-1进行验证,当然还要看除数n+1,n-1,素性纯度*/
if(a){if((m-1)%(n+1)==0)i=0;} /***一旦被整除就说明不是素数故素性为零即将i 赋值为零***/
if(b){if((m-1)%(n-1)==0)i=0;}
}
if(j){
/**如果j非零就对m+1即所谓6*t+1进行验证,当然还要看除数n+1,n-1,素性纯度*/
if(a){if((m+1)%(n+1)==0)j=0;} /***一旦被整除就说明不是素数故素性为零即将j 赋值为零***/
if(b){if((m+1)%(n-1)==0)j=0;}
}
if((i+j)==0)break;
/**如果已经知道6*t-1,6*t+1都不是素数了那就结束试除循环***/
}
if(j){cout<<m+1<<endl;z++;if(z>=num)break;}
if(i){cout<<m-1<<endl;z++;if(z>=num)break;}
}
}