高效生成 Python 内的素数并计算复杂度

Question

生成1到n的素数Python3.如何提高效率，复杂度如何？

输入：一个数字，最大（一个大数字）输出：从1到max的所有素数输出为列表形式，将为 [2,3,5,7,11,13,.......] 该代码尝试以高效的方式（最小时间复杂度）执行此任务。

from math import sqrt    
max = (10**6)*3
print("\nThis code prints all primes till: " , max , "\n")
list_primes=[2]

def am_i_prime(num):
    """
    Input/Parameter the function takes: An integer number
    Output: returns True, if the number is prime and False if not
    """ 
    decision=True
    i=0
    while(list_primes[i] <= sqrt(num)): #Till sqrt(n) to save comparisons
        if(num%list_primes[i]==0):
            decision=False
            break
                    #break is inserted so that we get out of comparisons faster
                    #Eg. for 1568, we should break from the loop as soon as we know that 1568%2==0
        i+=1
    return decision


for i in range(3,max,2):  #starts from 3 as our list contains 2 from the beginning
    if am_i_prime(i)==True:
    list_primes.append(i)  #if a number is found to be prime, we append it to our list of primes

print(list_primes)

我怎样才能让它更快？我在哪里可以改进？这段代码的时间复杂度是多少？哪些步骤效率低下？ Eratosthenes 筛法在哪些方面比这更有效？

前几次迭代的工作：-

我们有一个 list_primes，其中包含质数。它最初只包含 2.
我们转到下一个数字 3。3 可以被 list_primes 中的任何数字整除吗？不！我们将 3 添加到 list_primes。现在，list_primes=[2,3]
我们转到下一个数字 4。4 可以被 list_primes 中的任何数字整除吗？是的（4 可以被 2 整除）。所以，我们什么都不做。现在list_primes=[2,3]
我们转到下一个数字 5。5 可以被 list_primes 中的任何数字整除吗？不！我们将 5 添加到 list_primes。现在，list_primes=[2,3,5]
我们转到下一个数字 6。6 可以被 list_primes 中的任何数字整除吗？是的（6 可以被 2 整除，也可以被 3 整除）。所以，我们什么都不做。现在 list_primes=[2,3,5]
等等...

Answer 1

O(N**2)

大约来说，第一次调用am_I_prime进行1次比较，第二次进行2次，...，所以总计数为1 + 2 + ... + N，即(N * (N-1)) / 2，阶数为 N 平方。

Answer 2

有趣的是，它需要一个相当深的数学定理来证明你的算法是正确的。定理是："For every n ≥ 2, there is a prime number between n and n^2"。我知道它已经被证明，而且更严格的界限已经被证明，但我必须承认我自己不知道如何证明它。如果这个定理不正确，那么 am_i_prime 中的循环可以越过数组的边界。

≤k的素数个数为O(k/log k)——这又是一个很深奥的数学定理。再一次，我无法证明。

但是无论如何，大约有 n / log n 个素数到 n，对于这些素数，循环将迭代所有素数到 n^(1/2)，并且有 O (n^(1 /2) / log n) 个。

因此，仅对于素数，运行时间为 O (n^1.5 / log^2 n)，因此这是一个下限。通过一些努力，应该可以证明对于所有数字，运行时间渐近相同。

O(n^1.5 / log n) 显然是一个上限，但实验上找到所有素数≤ n 的划分数似乎是 ≤ 2 n^1.5 / log^2 n，其中log是自然对数.

Answer 3

以下对您的代码进行重新整理和优化，将在您原来代码的近 1/2 的时间内达到您的最大值。它将您的顶级循环和谓词函数组合到一个函数中以消除开销并更有效地管理平方（平方根）：

def get_primes(maximum):
    primes = []

    if maximum > 1:
        primes.append(2)
        squares = [4]

        for number in range(3, maximum, 2):
            i = 0

            while squares[i] <= number:
                if number % primes[i] == 0:
                    break

                i += 1
            else:  # no break
                primes.append(number)
                squares.append(number * number)

    return primes

maximum = 10 ** 6 * 3
print(get_primes(maximum))

但是，基于筛的算法可以轻松击败它（因为它避免了除法 and/or 乘法）。您的代码有一个错误：设置 max = 1 将创建列表 [2] 而不是空列表的正确答案。始终测试极限的两端。

高效生成 Python 内的素数并计算复杂度

Efficiently generate primes in Python and calculate complexity

algorithm

primes

time-complexity

sieve-of-eratosthenes