以模6为基本的素数算法

//--------------------------------------------------------------------------- #include <vcl.h> #pragma hdrstop #include "slnum_p.h" //--------------------------------------------------------------------------- #pragma package(smart_init) #pragma resource "*.dfm" TForm1 *Form1; slnum a,b,c; //--------------------------------------------------------------------------- __fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner) { } //--------------------------------------------------------------------------- //---------------从string类中取出字符串转换为char * ------------------------------- char * strtoa(String ss) { char *sa; sa=new char[strlen(ss.c_str())+1]; strcpy(sa,ss.c_str() ); return sa; } /*----------------------------------------------------------------------- 版权所有：贵州省天柱县二中 罗国文，邮编：556600，Email:xuefu998@yahoo.com.cn 本程序提供了一种关于素数判定的新算法，以这些基本函数为基础，可帮助我们 处理关于素数的许多命题。 版权声明：在您使用和推广本程序时尊重作者版权，不准在不经许可的情况下发表 -------------------------------------------------------------------------*/ slnum Test_1(slnum x) //求模2的倍数 { slnum n; n=x/2; return n; } int Test_2(slnum x) //判断x的余数，返回值{0，1} { int k; k=x.sl[0]%2; return k; } int Test_P(slnum n) //P素性检验 { slnum m("1"); slnum M; M=(n-1)/3; for(m=1;(m<=M);m=m+1) { if(n%(m*2+1)==m) return 0; } return 1; } //数x的素性检验，x为素数返回1，否则为0 int Test_X(slnum x) { if (Test_2(x)==0) return 0; if (x.arr_n ==1&&atol(x.soure )==1) return 0; slnum n; n=Test_1(x); return (Test_P(n)); } /* void Out_X(slnum a,slnum b) //输出[a,b]间的素数 { slnum x; Form1->Memo1->Lines->Clear(); if (a.arr_n ==1&&a.sl[0]<3) Form1->Memo1->Lines->Append('2'); if (a.arr_n ==1&&a.sl[0]<5) Form1->Memo1->Lines->Append('3'); for(x=a;x<=b;x=x+1) { if(Test_X(x)==1) Form1->Memo1->Lines->Append(x.soure );} } void Out_N1(slnum a,slnum b) //输出[a,b]间使6n+1为素的n值 { slnum n; for(n=a;n<=b;n=n+1) { if(Test_P(n,1)==1) cout<<n.soure <<endl;} } void Out_N_1(slnum a,slnum b) //输出[a,b]间使6n-1为素的n值 { slnum n; for(n=a;n<=b;n=n+1) { if(Test_P(n,-1)==1) cout<<n.soure<<endl;} } //输出[a,b]间的孪生素数 void Out_2P(slnum a,slnum b) { slnum n,n1,n2; n1=Test_1(a); n2=Test_1(b); for (n=n1;n<=n2;n=n+1) if(Test_P(n,-1)*Test_P(n,1)==1) cout<<"["<<n.soure<<":("<<n*6-1<<" , "<<n*6+1<<")]"<<endl; } //求出任意的大于4的整数m为中心的第一对素数 int Out_Q(slnum m) { slnum S;int s; slnum n, k; n=Test_1(m); S=(m%6); s=S.sl[0]; if(n==0)return 0 ; switch (s) { case 5 : for(k=0;k<n;k=k+1) {if(Test_P(n+k,-1)*Test_P(n-k,-1)==1) { cout<<"["<<m*2<<":("<<(n+k)*6-1<<" , "<<(n-k)*6-1<<")]"<<endl; return 0;} } cout<<"Not find this number!!"<<endl; case 4 : for(k=0;k<n;k=k+1) {if(Test_P(n+1+k,1)*Test_P(n-k,1)==1) { cout<<"["<<m*2<<":("<<(n+1+k)*6+1<<" , "<<(n-k)*6+1<<")]"<<endl; return 0;} if(Test_P(n+k,1)*Test_P(n+1-k,1)==1) { cout<<"["<<m*2<<":("<<(n+k)*6+1<<" , "<<(n+1-k)*6+1<<")]"<<endl; return 0;} } cout<<"Not find this number!!"<<endl; case 3 : for(k=0;k<n;k=k+1) {if(Test_P(n+1+k,1)*Test_P(n-k,-1)==1) { cout<<"["<<m*2<<":("<<(n+1+k)*6+1<<" , "<<(n-k)*6-1<<")]"<<endl; return 0;} if(Test_P(n+k,1)*Test_P(n+1-k,-1)==1) { cout<<"["<<m*2<<":("<<(n+k)*6+1<<" , "<<(n+1-k)*6-1<<")]"<<endl; return 0;} if(Test_P(n+1+k,-1)*Test_P(n-k,1)==1) { cout<<"["<<m*2<<":("<<(n+1+k)*6-1<<" , "<<(n-k)*6+1<<")]"<<endl; return 0;} if(Test_P(n+k,-1)*Test_P(n+1-k,1)==1) { cout<<"["<<m*2<<":("<<(n+k)*6-1<<" , "<<(n+1-k)*6+1<<")]"<<endl; return 0;} } cout<<"Not find this number!!"<<endl; case 2 : for(k=0 ; k < n ; k=k+1) {if(Test_P(n+1+k,-1)*Test_P(n-k,-1)==1) { cout<<"["<<m*2<<":("<<(n+1+k)*6-1<<" , " <<(n-k)*6-1<<")]"<<endl; return 0;} if(Test_P(n+k,-1)*Test_P(n+1-k,-1)==1) { cout<<"["<<m*2<<":("<<(n+k)*6-1<<" , "<<(n+1-k)*6-1<<")]"<<endl; return 0;} } cout<<"Not find this number!!"<<endl; case 1 : for(k=0;k<n;k=k+1) {if(Test_P(n+k,1)*Test_P(n-k,1)==1) {cout<<"["<<m*2<<":("<<(n+k)*6+1<<" , "<<(n-k)*6+1<<")]"<<endl; return 0; } } cout<<"Not find this number!!"<<endl; case 0 : for(k=0;k<n;k=k+1) {if(Test_P(n+k,1)*Test_P(n-k,-1)==1) { cout<<"["<<m*2<<":("<<(n+k)*6+1<<" , "<<(n-k)*6-1<<")]"<<endl; return 0;} if(Test_P(n+k,-1)*Test_P(n-k,1)==1) { cout<<"["<<m*2<<":("<<(n+k)*6-1<<" , "<<(n-k)*6+1<<")]"<<endl; return 0;} } cout<<"Not find this number!!"<<endl; } return 1; } */ void __fastcall TForm1::Button1Click(TObject *Sender) { slnum x; int i; Form1->Memo1->Lines->Clear(); if (a.arr_n ==1&&a.sl[0]<=2) { Form1->Memo1->Lines->Append('2'),i=1;} for(x=a;x<=b;x=x+1) if(Test_X(x)==1){++i; Form1->Memo1->Lines->Append(x.soure );} char *s,*ss; s=new char[65536]; ss=new char[65536]; strcpy(ss,"这个范围内的素数有："); ltoa(i,s,10); strcat(ss,s); strcat(ss,"个"); Form1->Label7->Caption =ss; } //--------------------------------------------------------------------------- void __fastcall TForm1::Edit2Exit(TObject *Sender) { b.setval(strtoa(Form1->Edit2->Text)); } //--------------------------------------------------------------------------- void __fastcall TForm1::Edit1Exit(TObject *Sender) { a.setval(strtoa(Form1->Edit1->Text)); } //--------------------------------------------------------------------------- void __fastcall TForm1::Button6Click(TObject *Sender) { slnum x; int i=0; Form1->Memo1->Lines->Clear(); for(x=a;x<=b;x=x+1) if(Test_P(x)==1){++i; Form1->Memo1->Lines->Append(x.soure );} char *s,*ss; s=new char[65536]; ss=new char[65536]; strcpy(ss,"这个范围内的Q数有："); ltoa(i,s,10); strcat(ss,s); strcat(ss,"个"); Form1->Label7->Caption =ss; } //---------------------------------------------------------------------------