首页 > 代码库 > poj3641:伪素数检测

poj3641:伪素数检测

知道miller robin 素数测试中的伪素数定义就可以很容易解决,详见总结帖

#include <iostream>#include<stdio.h>#include<algorithm>#include<time.h>#include<math.h>using namespace std;long long n;long long multi(long long a,long long b,long long m)//a*b%m{    long long res=0;    while(b>0)    {        if(b&1)            res=(res+a)%m;        b>>=1;        a=(a<<1)%m;    }    return res;}long long quickmod(long long a,long long b,long long m) //a^b%m{    long long res=1;    while(b)    {        if(b&1)            res=multi(res,a,m);        b>>=1;        a=multi(a,a,m);    }    return res;}bool isprime(long long n){    for(int i=2;i*i<=n;i++)    {        if(!(n%i))            return 0;    }    return 1;}int main(){    long long p,a;    while(scanf("%I64d%I64d",&p,&a),p+a)    {        if(isprime(p))        {            puts("no");            continue;        }        if(quickmod(a,p,p)==a)            puts("yes");        else            puts("no");    }    return 0;}

 

poj3641:伪素数检测