如何在Python中制作一个所有素数的无限生成器？

Question

我试图用 python 制作这个无限生成器：

import math
def all_primes():
    count = 2
    while True:
        flag = True
        for x in range(2, int(math.sqrt(count) + 1)):
            if count % x == 0: 
                flag = False
        
        if flag:
            yield count
        else:
            count += 1
            
for i in all_primes():
    print(i)

但在输出中它总是给我 2。这是为什么？

Answer 1

找到素数后不会增加计数，因此总是返回相同的值 (3)。

随着您的前进，您的素数生成器在每个素数之间花费的时间将越来越长。

这是一个更高效的无限素数生成器。它的灵感来自埃拉托斯特尼筛法，但使用字典仅在到达非素数时传播倍数，并将素数倍数移动到下一个尚未标记为非素数的倍数：

def genPrimes():
    yield 2                      # get the first prime out of the way
    skips      = dict()          # multiples to skip {Multiple:2xPrime}
    multiples  = ((p*p,2*p) for p in genPrimes()) # multiples of primes
    skipMark,_ = next(multiples)                  # skipping coverage
    N = 1                        # prime candidate (odd numbers)
    while True:
       N += 2                        # next prime candidate
       if N >= skipMark:                     # extend skips coverage
           skipMark,stride = next(multiples) # 1st multiple and stride
           skips[skipMark] = stride          
       if N in skips:                # not a prime (multiple of a prime)   
           stride   = skips.pop(N)   # get prime multiple steps
           multiple = N + stride     # advance skip to next multiple
           while multiple in skips:
               multiple += stride    # not already skipped
           skips[multiple] = stride
       else:                         # N is prime
           yield N                   # return it 

输出：

for p in genPrimes(): print(p)
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
...

skips 字典大约包含每个 √P 一个条目（其中 P 是迄今为止找到的素数数量），并且不需要预分配内存。这种方法以空间换取时间。

Answer 2

您的代码总是产生“3”的原因是“flag”始终为真。使用 int(math.sqrt(count)+1) 在 for 循环中进行数学运算，使得循环仅从 2 -> 2 进行。因此唯一检查的是 if 3 % 2 == 0 这永远不是 true 。因此 flag 始终为 false 并且计数永远不会增加。

Answer 3

那是因为 for 循环永远不会迭代。如果 count=3 那么

int(math.sqrt(count) + 1)

将返回 2，因此 for 循环的范围将是 (2,2)，因此它永远不会迭代，并且标志值不会改变，因此 count 值是永远都是一样的。

Answer 4

这是我使用威尔逊定理创建的素数生成器。我们可以受益于 python-3 的无限整数来计算运行阶乘。 :-)

# find primes p>2 using Wilson's theorem: (p-2)! = 1(mod p)
n = int(input("Input the number of prime numbers you want to generate (at least 2)? "))
from time import time
t = time()
p,m,f = 2,2,1
Primes = [1,2]
while m<n:
    p += 1
    f = f*(p-2)         
    if (f-p*(f//p))==1: 
        m += 1
        Primes.append(p)
print (Primes)
print ('{} primes generated in {} seconds'.format(n,time()-t))