Posted on 2010-08-20 01:14
Kevin_Zhang 閱讀(365)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
數(shù)論
#include"iostream"
#include"stdio.h"
#include"stdlib.h"
#include"time.h" //系統(tǒng)時(shí)間函數(shù)的頭文件
using namespace std;
int T;//the number of tests
int j,d,N;
void computejd(int n)//求j和d,這個(gè)是正確的，d為odd
{int m=n-1;
j=0;
while(1)
{
if(m%2==0){j++;m=m/2;}
else {d=m;break;}
}
return ;
}//right
int GetRand()//求隨機(jī)數(shù)，種子為系統(tǒng)時(shí)間
{
srand(time(NULL)) ;
int n = rand()%(N-1)+1;
return n ;
}//right
int main()
{
int k;
printf("輸入測試次數(shù)T：");
scanf("%d",&T);//right
for(int x=1;x<=T;x++)
{scanf("%d",&N);
computejd(N);
for(k=1000;k>0;k--)
{int b=GetRand();
int r0, r,r1,i;
r0=N-1;i=0;
r=1; r1=b%N;
for(int q=0; q<=31;q++)
{ if((d&1)==1) r=(r*r1)%N;
r1=(r1*r1)%N; d>>=1;
}
while(r!=1&&i<j)
{
r0=r;r=(r*r)%N;i++;
}
if(r==1||i>=j)
{
if(r==1&&r0==N-1)continue;
else break;
}
}
if(k==0)printf("prime\n");
else printf("not prime\n");
}//outside cycle
return 0;
}