?? 素數檢測.txt
字號:
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define NMAX 10005
#define MAX 99999999
#define PI 3.1415926
int witness1(int a,int m,int n)
{
int w;
if(m==0) return 1;
if(m==1) return a%n;
w=witness1(a,m/2,n);
w=(w*w)%n;
if(m%2==1) w=(w*a)%n;
return w;
}
int witness2(int a,int m,int n)
{
int x=1,y=a%m,t;
while(m!=0)
{
if(m%2==1) x=(x*y)%n;
t=y;
y=(y*y)%n;
if(y==1 && t!=1 && t!=n-1) return 1;
m/=2;
}
if(x!=1) return 1;
else return 0;
}
int miller_rabin(int x)
{
int i,a;
if(x==2) return 1;
for(i=1;i<=5;i++)
{
a=x-i-1;
if(a==0) continue;
if(witness2(a,x-1,x)==1) return 0;
}
return 1;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==1) printf("1 is error\n");
else if(miller_rabin(n)==1) printf("yes\n");
else printf("no\n");
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -