素数题目总结及mr判断素数( 三 ) _判断素数

算法解释：
-Rabin算法是目前主流的基于概率的素数测试算法，是基于费马小定理所产生的算法。
根据费马小定理:对于任何一个质数 P 和整数 a，其中 a 和 P 互质，那么有 a ^ ( P-1 )≡ 1 ( mod P) 。反过来说，如果我们取一个p（不知道是不是素数），如果此时恰好有一个a，使p满足 a ^ ( P-1 )≡ 1 ( mod P)，那么p是不是就一定是素数呢？
实际上，如果有 a 不满足同余式，就意味着 P 不是质数；如果多个 a 都满足同余式，我们就可以猜想 P 是质数
所以，现在我们所通过费马小定理推出判断质数 P 的方法是：在 2 ~ P-1（a=1 也没关系）中，随机选择数 a（大概5~10个，因为Rabin验证了的想法只需要5~10个数字的验证就够了），若 a 正好不满足 a ^ ( P-1 ) ≡ 1 ( mod P )，就说明 P 不是质数；如果多个 a 都满足，就说明 P 极大概率下是质数。
代码
#include #include #include #include #include #define ll long longusing namespace std;//计算a*b%modll mod_mul(ll a, ll b, ll n){ll cnt = 0LL;while(b){if(b&1LL) cnt = (cnt+a)%n;a=(a+a)%n;b >>= 1LL;}return cnt;}//计算a^b%modll mod_exp(ll a, ll b, ll n){ll res = 1LL;while(b){if(b&1LL) res = mod_mul(res,a,n);a = mod_mul(a,a,n);b >>= 1LL;}return res;}//Miller-Rabin测试，测试n是否为素数bool Miller_Rabin(ll n, int respat){if(n==2LL || n==3LL || n==5LL || n==7LL || n==11LL) return true;if(n==1 || !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n)) return false;int k = 0;ll d = n-1; //要求x^u%n 不为1一定不是素数while(!(d&1LL)){k++; d >>= 1LL;}srand((ll)time(0));for(int i = 0; i < respat; i ++) {ll a = rand()%(n-2)+2;//在[2,n)中取整数ll x = mod_exp(a,d,n);ll y = 0LL;for(int j = 0; j < k; j ++){y = mod_mul(x,x,n);if(1LL==y && 1LL!=x && n-1LL!=x)return false; //二次探测定理，这里如果y = 1则x必须等于 1//或n-1,否则可以判断不是素数x = y;}if(1LL != y) return false;//费马小定理}return true;}int main(){int n;cin>>n;if(Miller_Rabin(n,5))cout << "Yes\n";else cout << "No\n";return 0;}
唯一分解定理
设a=p1^c1*p2^c2*p3^c3*p4^c4……*pn^cn
那么数n的因子个数为(1+c1)*(1+c2)*(1+c3)*……*(1+cn) 。
数n的所有的因子之和为
【素数题目总结及mr判断素数】 。