持续施工中
补充内容
米勒拉宾质数检验
原理 判断一个数能被某数整除和倍数。
费马小定理 如果一个数x不能被m整除的必要条件是pow(m,x-1)%x==1,但是这不是充分条件。
考虑一个算法,可以不断对x的次方进行迭代,循环校验。
具体实现是这样的,检验x能否大概率被m整除的算法。
定义d=x-1;
首先计算pow(m,d)%x是否为1,为1继续,不为1返回。
循环检验d是否为偶数,如果为偶数就继续运算。
在循环中先除以2,再执行检验,注意 pow(m,d)%x==p-1时可以证明它不被整除,具体翻阅论文。
选择前12个质数在oi中进行就足够了!