ミラーラビン素数テスト
1685 ワード
ミラーラビン素数テストでは、単一の数が素数であるかどうかを迅速に測定できます.
まず定理を知る必要があります.
1. Fermaの小さい定理:ap-1≡1(mod p)の中でpは質量数です
そこで,1つの数nがある場合には,まず1,2,3および2,3の倍数(大量のデータを削除できる)であるか否かを判断し,このとき残りは奇数である.
n−1=2 rdとし,異なるaをとり,rに対して0から最大とし,ad≡1(mod n)を満たすようにし,ここでは状況を分ける.
1)dは奇数であり、残り1であれば素数である可能性がある
2)dは偶数であり,同余-1であれば素数である可能性がある
3)サイクル後に上記に該当しない場合は、必ず合数とする
また、aをとる値については、通常2,7,61で2^32の桁まで計算することができ、さらに大きくする必要がある場合は2,3,5,7,11を計算する.
テンプレート問題hdu 2138.
まず定理を知る必要があります.
1. Fermaの小さい定理:ap-1≡1(mod p)の中でpは質量数です
そこで,1つの数nがある場合には,まず1,2,3および2,3の倍数(大量のデータを削除できる)であるか否かを判断し,このとき残りは奇数である.
n−1=2 rdとし,異なるaをとり,rに対して0から最大とし,ad≡1(mod n)を満たすようにし,ここでは状況を分ける.
1)dは奇数であり、残り1であれば素数である可能性がある
2)dは偶数であり,同余-1であれば素数である可能性がある
3)サイクル後に上記に該当しない場合は、必ず合数とする
また、aをとる値については、通常2,7,61で2^32の桁まで計算することができ、さらに大きくする必要がある場合は2,3,5,7,11を計算する.
テンプレート問題hdu 2138.
#include <cstdio>
int t,n,ans;
long long qpow(int x,int y,int mod)
{
long long ans=1,a=x;
while(y)
{
if(y&1) ans=ans*a%mod;
a=a*a%mod;
y>>=1;
}
return ans;
}
bool MR_prime(int a,int n)
{
int r=0,d=n-1;
if(!(n%a)) return false;
while(!(d&1))
{
d>>=1;
r++;
}
long long k=qpow(a,d,n);
if(k==1) return true;
for(int i=0;i<r;i++,k=k*k%n) if(k==n-1) return true;
return false;
}
bool check_prime(int n)
{
if(n==2||n==3) return true;
if(!(n&1)||n%3==0||n==1) return false;
if(MR_prime(2,n)&&MR_prime(7,n)&&MR_prime(61,n)) return true;
return false;
}
int main()
{
while(scanf("%d",&t)!=EOF)
{
ans=0;
while(t--)
{
scanf("%d",&n);
if(check_prime(n)) ++ans;
}
printf("%d
",ans);
}
return 0;
}