测试一个数字是否为质数的最快方法？ [英] Fastest way of testing if a number is prime?

问题描述

我正在尝试使用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`

推荐答案

直到平方根大约是您能想到的最简单的除法。它最糟糕的情况是质数，因为所有除法都必须执行。无论如何，在十亿之前，几乎没有可测量的时间(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

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

某些微优化是可能的(例如使用增量表)，但我认为它们不会产生很大的收益。

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

这篇关于测试一个数字是否为质数的最快方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！