给出一个64位的大数,如何快速判断其是否为素数

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
LL n,m;
//****************************************************************
// Miller_Rabin 算法进行素数测试
//速度快,而且可以判断 <2^63的数
//****************************************************************
const int S=20;//随机算法判定次数,S越大,判错概率越小 LL mult_mod(LL a,LL b,LL mod) //(a*b)%c a,b,c<2^63
{
a%=mod;
b%=mod;
LL ans=0;
while(b)
{
if(b&1)
{
ans=ans+a;
if(ans>=mod)
ans=ans-mod;
}
a=a<<1;
if(a>=mod) a=a-mod;
b=b>>1;
}
return ans;
} LL pow_mod(LL a,LL b,LL mod) // a^b%mod
{
LL ans=1;
a=a%mod;
while(b)
{
if(b&1)
{
ans=mult_mod(ans,a,mod);
}
a=mult_mod(a,a,mod);
b=b>>1;
}
return ans;
} //以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数
//一定是合数返回true,不一定返回false bool check(LL a,LL n,LL x,LL t)
{
LL ret=pow_mod(a,x,n);
LL last=ret;
for(int i=1;i<=t;i++)
{
ret=mult_mod(ret,ret,n);
if(ret==1 && last!=1 && last!=n-1) return true;//合数
last=ret;
}
if(ret!=1) return true;
else return false;
} // Miller_Rabin()算法素数判定
//是素数返回true.(可能是伪素数,但概率极小)
//合数返回false; bool Miller_Rabin(long long n)
{
if(n<2)return false;
if(n==2) return true;
if( (n&1)==0) return false;//偶数
LL x=n-1;
LL t=0;
while( (x&1)==0 ) { x>>=1;t++;}
for(int i=0;i<S;i++)
{
LL a=rand()%(n-1)+1;//rand()需要stdlib.h头文件
if(check(a,n,x,t))
return false;//合数
}
return true;
}
int main()
{
// n,m;
while(scanf("%lld%lld",&n,&m)>0)
{
LL sum=0;
for(LL i=0; i<m; i++)
{
sum+=(LL)(pow((double)(n),i)+0.5);
}
//printf("%lld\n",sum);
if(Miller_Rabin(sum))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}

  

最新文章

  1. 关于mysql数据库插入数据,不能插入中文和出现中文乱码问题
  2. iOS & Mac JSON To Model
  3. 加州大学伯克利分校Stat2.3x Inference 统计推断学习笔记: Section 4 Dependent Samples
  4. JSP动作标签
  5. 轻量型ORM框架Dapper的使用
  6. JavaWeb学习----JSTL标签库
  7. RT-Thread的CPU使用率计算
  8. SmartZoneOCR识别控件免费下载地址
  9. fiddler代理
  10. 委托学习续:Action、Func和Predicate
  11. 使用python实现最优化问题
  12. 关于MYSQL优化(持续更新)
  13. Ubuntu频率较高的操作
  14. (转)反射发送实战(-)InvokeMember
  15. Cacti 是一套基于PHP,MySQL,SNMP及RRDTool开发的网络流量监测图形分析工具
  16. set集合容器
  17. 1648: [Usaco2006 Dec]Cow Picnic 奶牛野餐
  18. super函数没有那么简单-super原理剖析
  19. 非常适用的Sourceinsight插件,提高效率【强力推荐】
  20. nfs服务启动失败:Failed to start NFS status monitor for NFSv2/3 locking..

热门文章

  1. Nginx 和 PHP 的两种部署方式比较
  2. 归并排序(C++实现)
  3. GDataXMLNode:xml解析库
  4. SDL相关学习
  5. EF GroupBy 根据key 分组 再把key求和(取决于每条数据中 arr的条数) arr 中有多少条数据 就把多少个key 加起来
  6. oracle三大范式(转载)
  7. 【转】Oracle回收站(recyclebin)
  8. mongodb 远程访问配置
  9. unity, Collider2D.attachedRigidbody
  10. jquery 获取URL参数并转码的例子