随机产生大素数的C++程序

#include <iostream.h> #include <stdlib.h> #include <time.h> #include <math.h> bool witness(int a,long n) { //得到n-1的二进制表示 int div=(int) n; int b[128]; int k=0; int i; while(div!=0) { b[k]=div%2; div=div/2; k++; } //计算 int x; int d=1; for(i=k-1;i>=0;i--) { x=d; d=(d*d)%n; if(d==1&&x!=1&&x!=n-1) return true; if(b[i]==1) d=(d*a)%n; } if(d!=1) return true; else return false; } int main() { long digit; int a; int i=0; int j; srand( (unsigned)time( NULL ) ); //以时间为获得产生随机数的种子 while(1) { digit=rand(); while(digit%2==0) digit=rand(); //随机产生一个奇数 cout<<"the cow prime is "<<digit<<"\n"; /* i=0; while(i<digit) { //a为小于digit的随机数 a=(int)(digit/(float)RAND_MAX * rand()); cout<<a<<"\n"; //素数测试（Miller_Rabin测试法），返回true表示不是素数 if(witness(a,digit)) break; i++; } */ for(i=2;i<=sqrt(digit);i++) { if(digit%i==0) break; } cout<<"i="<<i<<"\n"; if(i+1 rel='nofollow' onclick='return false;'>(int)sqrt(digit)) { cout<<"digit "<<digit<<" is big prime!\n"; break; } } return 0; }