蒙特卡罗法判断素数(质数)

问题重述: 给定一个正整数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 蒙特卡罗法: 随机产生问题的解,但在产生的解中,有一部分可以判断真假,一部分不能判断真假。对于不能