首页 > 代码库 > 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:伪素数检测
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。