测试一个数字是否为质数最快的方法是什么？

Question

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

我有两个函数可以实现这个功能。它们都返回True或False。

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

isPrime2函数在返回素数的True时更快。但是，如果某个数字很大且不是素数，则需要花费很长时间才能返回一个值。第一个函数对此效果更好。

如何设计一种解决方案，可以快速返回一个大数值是否不是素数，并且对于大素数也可快速处理？

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`

- numersoz

---

https://en.wikipedia.org/wiki/Primality_test - Ry-

使用一个预先初始化的布隆过滤器，其中包含了一系列素数，这些素数的范围应该覆盖到你需要考虑的最大值。 - Mark Ransom

有多大？请非常具体，因为答案将直接取决于此。 - user1196549

@RoryDaulton：不确定这是一个好的重复问题。素性测试比完整的因式分解问题更容易。 - Mark Dickinson

仍然是错误的重复。分解质因数和素性检测不是同一件事情。检查一个1000位数是否（可能）为质数非常快速；对于这样一个数做一个确定性的素性检查会慢一些，但仍然可行。但这已经远超出了有效分解的范围。 - Mark Dickinson

Answer 1

穷举到平方根是你能想到的最简单的方法。最坏情况是针对质数的，因为需要进行所有除法。无论如何，在十亿以内，时间几乎没有可测量的（约为 1000000007 的1.2毫秒）。

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

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

可以进行一些微小的优化（例如使用增量表），但我认为它们无法产生大的收益。

有更复杂和更快的方法可用，但我不确定它们是否值得为如此小的n费心。

- user1196549

---

@KellyBundy：将其重命名为FirstPrimeFactor。祝你有个愉快的一天。 - user1196549

好的，更好了。仍然有些不方便和容易出错，需要在实际素性检查之外添加额外的逻辑。有人可能认为 FirstPrimeFactor(n) == n 就可以了，但这会让 1 看起来是质数。实际上，FirstPrimeFactor(1) 返回 1 已经不好了，因为 1 只是不是一个质因子。我认为 None 应该是正确的结果，尽管这对调用者来说也很不方便。我想 2 <= n == FirstPrimeFactor(n) 是使用它的正确方式，可能需要说明一下。 - Kelly Bundy

@KellyBundy：请调查 n == 0 和 n < 0 的情况。 - user1196549

我已经有了。他们呢？不支持负数是合理的，对于n=0返回2也是合理的。 - Kelly Bundy

@KellyBundy：嗯，这使得自然数b的已知属性a≤a.b无效。我应该删除我的答案吗？ - user1196549

Answer 2

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

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

有趣的是，isPrime2存在缺陷。它对6、10、12等返回True。

第3到6行非常说明问题。

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

当找到数字d的因子时，将更新number为number = number // d，在while循环结束时，如果number > 1，则返回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

- Xero Smith

---

isPrime1是我编写的一个函数，而isPrime2是我修改的一个旨在计算一个数的质因数的函数。第一个函数可以正常工作，让我来修复第二个函数。谢谢。 - numersoz

Answer 3

这是我想出来的

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

- ephrim

---

你好，以下是編程相關內容的中文翻譯：haufa。你的函數第一行與註釋不符。部分“not number % 2”將對所有奇數返回False，這意味著它將對除2以外的每個質數都返回False。請相應修改該函數。 - Xero Smith

你的函数比我的第一个函数快。isPrime1(1000000007)用了70秒得出结果，而is_Prime(1000000007)用了60秒得出结果。这很不错，但让我们看看其他人是否有更快的解决方案。 - numersoz

@XeroSmith，我已经做出了更改。感谢您的纠正。 - ephrim

测试到 number 是完全浪费时间的。你可以在 √number 处停止。对于 1000000007，这样做大约快了 30000 倍。 - user1196549

为什么你只需要计算到平方根？ - Hacker