蒙特卡罗法判断素数（质数）
问题重述：
作者：周者
给定一个正整数n ( >= 3), 判断是不是素数。
思路介绍使用蒙特卡罗法算法结合费尔马小定理结合二次探测定理。
费尔马小定理：如果p是素数，则有 ap−1 mod p=1a^{p-1} \; mod \; p = 1ap−1modp=1, a∈[2,p−1]a\in[2,p-1]a∈[2,p−1]
二次探测定理：如果p是素数，则方程x2 mod p=1x^2 \; mod \; p = 1x2modp=1 的解是 x=1x=1x=1 或 x=p−1x=p-1x=p−1
蒙特卡罗法： 随机产生问题的解，但在产生的解中，有一部分可以判断真假，一部分不能判断真假。对于不能判断的，则可能是错误的解。随着多次调用此算法，由于每次调用都是独立的，因此产生错误解的概率越来越小。
例如使用费尔马小定理，随机产生一个aaa, 如果不满足定理要求，则ppp是合数，否则不能判定其是素数还是合数，如果认定为素数，则有一定的概率是错误的。但随着多次如上过程的进行，错误概率越来越小）。
运行结果如下：
判断 3~100哪些是素数，并输出素数。
代码如下：
#include
#include
using namespace std;
/* 求次方
* a : 随机产生的底数
* p : 指要计算 a^p
* n : 要判断的数
* */
int func(int a, int p, int n){
if(p == 1){
return a;
}
//二次探测
if(p * p % n == 1 && p != n - 1){
return 0;
}
return a * func(a, p - 1, n) % n;
}
/* 判断一个数是否是质数(n>=3)
* */
bool prime(int n){
srand(0);
for(int i = 0; i < 100; i++){ //循环100次，使得错误概率足够小
//费尔马小定理
int a = rand() % (n - 2) + 2;
int temp = func(a, n - 1, n);
if(temp == 0 || temp != 1){
return false;
}
}
return true;
}
int main(){
for(int i = 3; i < 100; i++){
if(prime(i)){
cout << i << " ";
}
}
return 0;
}
作者：周者
