Miller Robin大素数判定
2024-10-06 22:34:49
Miller Robin算法
当要判断的数过大,以至于根n的算法不可行时,可以采用这种方法来判定素数。
用于判断大于2的奇数(2和偶数需要手动判断),是概率意义上的判定,因此需要做多次来减少出错概率。
Template:
```C++
typedef long long ll;
ll kmul(ll a,ll b,ll mod)
{
ll res=0;
while (b)
{
if (b&1)
res=(res+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return res;
}
ll kpow(ll a,ll b,ll mod)
{
ll res=1;
while (b)
{
if (b&1)
res=kmul(res,a,mod)%mod;
a=kmul(a,a,mod)%mod;
b>>=1;
}
return res;
}
bool Mil_Rb(ll n,ll a)
{
ll d=n-1,s=0,i;
while (!(d&1))
{
d>>=1;
s++;
}
ll t=kpow(a,d,n);
if (t==1||t==-1)
return 1;
for (i=0;ia[i]&&!Mil_Rb(n,a[i]))
return 0;
}
return 1;
}
```
最新文章
- SecureCRT如何与Linux虚拟机进行关联
- java异常面试题
- Gvr SDK for Unity 分析(一)
- 二模 (8) day2
- jQuery easyui 提示框
- Samba服务器安装及配置
- 免费的天气预报API--谷歌,雅虎,中央气象台
- 【Java基础】Java异常的一些总结
- apache配置重写
- TCP的核心系列 — SACK和DSACK的实现(三)
- elbow 求拐点
- 小白的CTF学习之路2——二进制数据基础与运算(上)
- el取bean 对象属性规则
- java垃圾回收诡异现象
- LOJ 6485 LJJ学多项式
- Excel添加下拉菜单
- 【转载】Android dip,px,pt,sp 的区别
- 使用Octopress博客 搭建博客
- Android四种数据存储方式
- seajs源码分析(一)---整体结构以及module.js