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 = ;
while (n>)
{
if (n&) b=(b*m)%k;
n=n>>;
m=(m*m)%k;
}
return b;
} bool Miller_Rabbin(long long t)
{
if (t==) return true;
if (power(,t-,t)!=) return false;
if (power(,t-,t)!=) return false;
if (power(,t-,t)!=) return false;
return true;
} int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int x,ans;
ans=;
for (int i=; i<n; i++)
{
scanf("%d",&x);
if (Miller_Rabbin(x)) ans++;
}
printf("%d\n",ans);
}
}
上一篇:TextView——setCompoundDrawables说明


下一篇:Emgu.CV(二)