洗尘斋

三悬明镜垂鸿韵,九撩清泉洗尘心

常用链接

统计

最新评论

素数算法

今天看到一个素数的算法,利用素数集中在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;}
        }

}

posted on 2007-09-08 21:00 芥之舟 阅读(857) 评论(0)  编辑 收藏 引用 所属分类: 数据结构和算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理