LOJ 143(Miller Rabin素数試験)
1360 ワード
LOJ143
标题:1 e 5個(1 e 18)の数で、それぞれ質素かどうかを判断します.
标题解:Miller Rabin素数テスト(フェルマ小定理,二次プローブ)被試験数がある範囲内にある場合、MillerRabin素数試験がこの範囲内の各数に対して正確に結果を得るために適切な試験底数を選択することができる.以下はウィキペディアからaを選択する方法です. N<4759123141がa=2,7,61を選択すると、アルゴリズムが正しい結果を得ることが保証される. N<382512305546413051≒3∗10^18 a=2,3,5,7,11,13,17,19,23を選択すると、アルゴリズムが正しい結果を得ることができる. N<18446744073709551616=2^64 a=2,3,5,7,11,13,17,19,23,29,31,37を選択すると、アルゴリズムが正しい結果を出すことが保証される .
标题:1 e 5個(1 e 18)の数で、それぞれ質素かどうかを判断します.
标题解:Miller Rabin素数テスト(フェルマ小定理,二次プローブ)
#include
#define ll long long
#define i128 __int128
using namespace std;
ll n;
int primes[19]={2,3,5,7,11,13,17,19,23,29,31,37};
ll poww(ll a,ll b,ll c){
ll ans=1;i128 base=a;
while(b){
if(b&1)ans=ans*base%c;
base=base*base%c;
b>>=1;
}
return ans;
}
bool miller_rabin(ll n){
for(int i=0;i<=8;i++){
if(primes[i]==n)return 1;
else if(primes[i]>n)return 0;
ll t=poww(primes[i],n-1,n),x=n-1;
if(t!=1)return 0;
while(t==1&&x%2==0){
x/=2;
t=poww(primes[i],x,n);
if(t!=1&&t!=n-1)return 0;
}
}
return 1;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
while(cin>>n){
if(miller_rabin(n))puts("Y");else puts("N");
}
return 0;
}