如何固定算法以计算 Python 中的素数

Question

这是我的代码：

import math

n=100

prime=[]
[prime.append(i) for i in range(2,n)]
i=2

"""for i in range(2,int(math.sqrt(n))):"""
while i*i <= n:
    for j in range(2,n+1):
        if i * j in prime:
            prime.remove(i*j)
    i +=1

print(prime)

现在这行得通了，但是当我将 n 从 100 更改为 10000 时，它就崩溃了。我该如何固定它还是应该使用发电机方式？谢谢。

Answer 1

我用过：

def gen_primes():
    D = {}

    q = 2

    while True:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1

从旧的 post 那里得到它...我会寻找它并在找到它时记下它，

Answer 2

我们可以只用一个循环来完成：

num = 407
if num > 1:
   for i in range(2,num):
       if (num % i) == 0:
           print(num,"is not a prime number")
           print(i,"times",num//i,"is",num)
           break
   else:
       print(num,"is a prime number")
else:
   print(num,"is not a prime number")

Answer 3

时间激增的原因是您使用的数据结构使其成为 O(n^2) 算法。

使用 set 将允许等效逻辑，同时将其简化为 O(n) 算法：

import math

n=100

prime = set(i for i in range(2,n))
i=2

while i*i <= n:
    for j in range(2,n+1):
        if i * j in prime:
            prime.remove(i*j)
    i +=1

print(prime)

特别昂贵的操作是i * j in prime。如果 prime 是一个列表，它可能必须扫描整个列表。对于集合，它不必扫描所有元素。

如何固定算法以计算 Python 中的素数

How to fasten algorithm to calculate Prime Numbers in Python

python

algorithm

primes

sieve-of-eratosthenes

python-3.x