判斷偽素數(shù)
#include <stdio.h>
#include <math.h>
int quick_mod (int a, int b, int mod)
{
int ans = 1;
a = a % mod;
while(b>0) {
if(b % 2 == 1)
ans = (ans * a) % mod;
b = b/2;
a = (a * a) % mod;
}
return ans;
}
int isprime (long long p)
{
long long i;
for(i=2;i<=sqrt(p);i++)
if(p % i == 0)
return 0;
return 1;
}
int main(int argc, char *argv[])
{
long long a,p;
while(scanf("%lld%lld",&p,&a)!=EOF && (a!=0 || p!=0))
{
if (isprime(p))
printf("no\n");
else
{
if(quick_mod(a,p,p) == a)
printf("yes\n");
else
printf("no\n");
}
}
return 0;
}
