模幂运算

2019-04-13 12:42发布

站内文章 / 模拟电子
11628 0 1637
//一开始写错了是因为模幂运算溢出 #include #include #define mistakeP 0.0001 using namespace std; bool Btest(int a,int n) {int s=0; int t=n-1; do{ s++; t=t/2; }while(t % 2!=1); //int x=((int)pow(a,t))%n; int x=1; for(int i=0;iif(x==1 || x==n-1) {return true; } for(int i=1;i<=s-1;i++) {x=x*x%n; if(x==n-1) return true; } return false; } bool MillRab(int n) {int a=rand()%(n-3)+2;//n need large than 3 return Btest(a,n); } bool repeatMillRab(int n,int k) {for(int i=0;iif(MillRab(n)==false) return false; } return true; } int printPrimes() { cout<<"2 3 "; int n=5; int count=0; while(n<10000) {if(repeatMillRab(n,(int)(log2(1.0/mistakeP)/2))) {cout<" "; if(n>100) count++; } n=n+2; } cout<return count; } bool judgePrime(int n) {for(int i=2;i<=(int)pow(n,0.5);i++) {if(n%i==0) return false; } return true; } int accuratePrimes() {int count=0; for(int i=2;i<=10000;i++) {if(judgePrime(i)) {cout<" "; if(i>100) count++; } } cout<return count; } int main() {cout<<"repeatMillRab:"<int c1=printPrimes(); cout<<"accurate:"<int c2=accuratePrimes(); cout<cout<<"100~10000"<<"repeatMillRab: "<" accurate: "<cout<<"deviation: "<<((float)(c2-c1))/c2<

热门文章