素数测试

给定一个数字n,检测n是否是一个素数。
最简单的方法就是尝试从2到 n的平方根 是否整除N。

def isPrime(n):
    for i in range(2, int(pow(n, 0.5))):
        if n % i == 0:
            return False
    return True

另一种方法就是米勒-拉宾素数测试：
一个数字n为素数的必要条件是对于任意a<n，都有 ( a^(n-1) ) mod n = 1
需要注意的是这一个必要条件。当n是素数的时候等式成立。
但是当等式成立的时候 n 有75%的可能性是素数。
我们可以通过多次执行这个测试来迅速的排出一些不是质数的家伙。
但是通过测试的数字仍然必须用第一种方式来检测才能确定n是一个素数。

import random
def MRTest(n):
    for i in range(4):
        a = random.randomint(2, n-1)
        if pow(a, n-1, n) != 1:
            return False
    return isPrime(n)