前 100 个素数

Question

我知道有多种方法可以找到前 100 个素数，但请帮助我采用我的方法。我发现 的值count正在增加，但由于某种原因while循环条件不适用：

count = 0

while(count <= 20):
    for i in range(2, 20):
        for j in range(2, i):
            if i < j:
                print("The number",i,"is prime")
            elif i % j == 0:
                break
        else:
            print("The number",i,"is prime")
            count = count + 1
            print(count)

Answer 1

您可以使用埃拉托斯特尼筛法来查找第一个n素数：

def primes_upto(limit):
    prime = [True] * limit
    for n in range(2, limit):
        if prime[n]:
            yield n # n is a prime
            for c in range(n*n, limit, n):
                prime[c] = False # mark composites

要获得前 100 个素数：

>>> list(primes_upto(542))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, ... ,
 499, 503, 509, 521, 523, 541]

要找到第一个n素数，您可以估计第 n 个素数（将上限作为限制）或使用无限素数生成器并获得所需数量的数字，例如使用list(itertools.islice(gen, 100)).