测试数字是否为质数的最快方法？

Question

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

我有两个功能可以做到这一点。 return True 或 False。

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

函数 isPrime2 在 return 对素数为真时速度更快。但是，如果一个数字很大并且不是质数，那么 return 一个值需要很长时间。第一个函数与它配合得更好。

我怎样才能想出一个解决方案，它可以快速 return 对于非素数的大数来说是错误的，并且可以快速处理一个大的素数？

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

素数测试是一个非常棘手的话题。

在尝试加速您的代码之前，请尝试确保它按预期工作。我建议您从非常简单的算法开始，然后从那里构建。

有趣的是，isPrime2 存在缺陷。 return对于 6、10、12 是正确的...

第 3 到 6 行非常有说服力

while d*d <= number:
    while (number % d) == 0:            
        number //= d
    d += 1

当找到 number d 的因数时，number 更新为 number = number // d 并且在 while 循环结束时，如果 number > 1 你 return True

使用 number = 6 完成代码：

isPrime2(6)
initialise> number := 6
initialise> d := 2
line3> check (2 * 2 < 6)     :True
line4> check (6 % 2 == 0)    :True
line5> update (number := 6//2) -> number = 3
line6> update (d : d + 1) -> d = 3
jump to line3
line3> check (3 * 3 < 3)      :False -> GOTO line7
line7> check(number > 1) -> check(3 > 1) :True
line8> return True -> 6 is prime

Answer 2

这是我想出的

def is_prime(number):
    # if number is equal to or less than 1, return False
    if number <= 1:
        return False

    for x in range(2, number):
        # if number is divisble by x, return False
        if not number % x:
            return False
    return True

Answer 3

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

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

请注意，此版本 returns 最小除数或 0 而不是布尔值。

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

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

测试数字是否为质数的最快方法？

Fastest way of testing if a number is prime?

python

math

primes