HDU 2138 How many prime numbers

米勒罗宾素数测试：

/*
  if n < 1,373,653, it is enough to test a = 2 and 3.
  if n < 9,080,191, it is enough to test a = 31 and 73.
  if n < 4,759,123,141, it is enough to test a = 2, 7, and 61.
  if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11.
*/
#include <cstdio>
long long power(long long m,long long n,long long k)
{
    long long b = 1;
    while (n>0)
    {
        if (n&1) b=(b*m)%k;
        n=n>>1;
        m=(m*m)%k;
    }
    return b;
} 

bool Miller_Rabbin(long long t)
{
    if (t==2) return true;
    if (power(2,t-1,t)!=1) return false;
    if (power(7,t-1,t)!=1) return false;
    if (power(61,t-1,t)!=1) return false;
    return true;
}
    
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int x,ans;
        ans=0;
        for (int i=0; i<n; i++)
        {
            scanf("%d",&x);
            if (Miller_Rabbin(x)) ans++;
        }
        printf("%d
",ans);
    }    
}