打印连续素数

Question

我正在尝试用Python创建一个程序来打印连续的素数。在

estPrimes = [2, 3]
num = 3
run = True

while run == True:
    for i in range(estPrimes[0], estPrimes[(len(estPrimes) - 1)]):
        if i % num == 0:
            num += 2
            sleep(1)
        else:
            estPrimes.append(num)
            print(num)
            sleep(1)
            num += 2

它只会以2为单位打印，我知道这与num += 2有关，但是，为什么它不除以estPrimes列表呢？在

Answer 1

从哪里开始？在

• 您正在编辑列表，同时对其进行迭代。那通常是病 有人建议会有奇怪的虫子。

• 你增加num无论你的情况如何，这是你的主要问题

• 你要检查你找到的第一个素数和最后一个素数之间的每一个数，而不仅仅是质数

---

这是你的代码修正

def print_primes_to(n):

    primes = [2,3]
    for prime in primes:
        print(prime)

    for num in range(5, n, 2):
        isprime = True
        for prime in primes:
            if num % prime == 0: #not prime
                isprime = False
                break
        if isprime:  # could replace with for/else
            primes.append(num)
            print(num)

测试用例

^{pr2}$

---

有更好的算法，这里有一个我在附近的：

import itertools as _itertools

def primelist(n):
    """Returns a list of all primes less than n."""
    if n <= 2:
        return []
    nums = [True]*(n - 2)
    for num in range(2, _rootp1(n)):
        for counter in _itertools.count(num):
            product = counter * num
            if product >= n:
                break
            nums[product - 2] = False
    return [index for index, val in enumerate(nums, 2) if val]

def _rootp1(n: float) -> int:
    """returns the truncated square root of n plus 1 for use in range"""
    return int(n**0.5) + 1

看看生成所有小于100万的素数需要多长时间

%timeit primelist(1_000_000)  
1.33 s ± 30.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)