用 Python 测试一个数是否为质数的最快方法

Question

我正在尝试使用 Python 快速确定一个数字是否为质数。

我有两个功能可以做到这一点。两者都返回 True 或 False。

函数 isPrime1 返回 False 的速度非常快，是一个数字不是素数。例如有一个大数字。但是对于大素数测试 True 的速度很慢。

函数 isPrime2 在为素数返回 True 时更快。但是如果一个数很大而且不是质数，那么返回一个值需要很长时间。第一个函数可以更好地工作。

我怎样才能想出一个解决方案，该解决方案可以快速为非质数的大数返回 False 并且可以快速处理质数的大数？

`

def isPrime1(number): #Works well with big numbers that are not prime
    state = True
    if number <= 0:
        state = False
        return state
    else:          
        for i in range(2,number):
            if number % i == 0:
                state = False
                break
        return state

def isPrime2(number): #Works well with big numbers that are prime   
    d = 2
    while d*d <= number:
        while (number % d) == 0:            
            number //= d
        d += 1
    if number > 1:       
        return True
    else:
        return False`

Answer 1

直到平方根的穷举除法大约是您能想到的最简单的。最坏的情况是素数，因为必须执行所有除法。无论如何，直到 10 亿，几乎没有可测量的时间（大约 1.2 毫秒1000000007）。

def Prime(n):
    if n & 1 == 0:
        return 2
    d= 3
    while d * d <= n:
        if n % d == 0:
            return d
        d= d + 2
    return 0

请注意，此版本返回最小的除数，0而不是布尔值。

一些微优化是可能的（例如使用增量表），但我认为它们可以产生很大的收益。

有更复杂和更快的方法可用，但我不确定它们是否值得为这么小的n.