ミラーラビン素数テスト

ミラーラビン素数テストでは、単一の数が素数であるかどうかを迅速に測定できます.
まず定理を知る必要があります.
　　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;
}