今天看到一個(gè)素?cái)?shù)的算法，利用素?cái)?shù)集中在6x+1/6x-1的原理
整理了一下 算法如下 打印max以下num個(gè)素?cái)?shù)：
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的值 是是否進(jìn)行驗(yàn)證的標(biāo)志也是對(duì)應(yīng)的6t-1和6t+1的素性標(biāo)志**/
if(((k-4)==0)||((k-9)==0)||((m+1)%3==0))j=0;
/*此處是簡(jiǎn)單驗(yàn)證6*t-1,6*t+1 是不是素?cái)?shù)，借以提高素?cái)?shù)純度**/
if(((k-6)==0)||((m-1)%3==0))i=0;
/***先通過(guò)初步判斷去除末尾是5，及被3整除的數(shù)***/
for(p=1;p*6<=sqrt(m+1)+2;p++ )
{
n=p*6;
/**將6*p-1和6*p+1看作偽素?cái)?shù)來(lái)試除*****/
k=p%10;
a=1;b=1;
/**同樣此處a,b的值也是用來(lái)判斷除數(shù)是否為素?cái)?shù)提高除數(shù)的素?cái)?shù)純度**/
if(((k-4)==0)||((k-9)==0))a=0;
if(((k-6)==0))b=0;
if(i){
/*如果i非零就對(duì)m-1即所謂6*t-1進(jìn)行驗(yàn)證，當(dāng)然還要看除數(shù)n+1,n-1,素性純度*/
if(a){if((m-1)%(n+1)==0)i=0;} /***一旦被整除就說(shuō)明不是素?cái)?shù)故素性為零即將i 賦值為零***/
if(b){if((m-1)%(n-1)==0)i=0;}
}
if(j){
/**如果j非零就對(duì)m+1即所謂6*t+1進(jìn)行驗(yàn)證，當(dāng)然還要看除數(shù)n+1,n-1,素性純度*/
if(a){if((m+1)%(n+1)==0)j=0;} /***一旦被整除就說(shuō)明不是素?cái)?shù)故素性為零即將j 賦值為零***/
if(b){if((m+1)%(n-1)==0)j=0;}
}
if((i+j)==0)break;
/**如果已經(jīng)知道6*t-1,6*t+1都不是素?cái)?shù)了那就結(jié)束試除循環(huán)***/
}
if(j){cout<<m+1<<endl;z++;if(z>=num)break;}
if(i){cout<<m-1<<endl;z++;if(z>=num)break;}
}
}