Python中的质数

Question

我在尝试写一个程序，目的是显示2到200之间的所有质数。

这是我写的程序。

liste = [ ]
liste.append(2)
liste = [2]

for primeCandidate in range (2,10):
    isPrime = True
    for divisor in range (2,primeCandidate):
        if primeCandidate % divisor == 0:
            isPrime = False
            break
        if isPrime:
            liste.append(primeCandidate)
            print(liste)

但是我总是得到错误的结果。我找不到我的错误。你能帮我找出我的错误吗？

Answer 1

from math import sqrt


def isPrime(num) :
    if num in [2,  3 ] : return True
    elif num < 2: return False 
    for i in [2]  +  range(3, int(sqrt(num)),  2) :
        if not num % i: return False 
    return True 

liste = [i for i in range(2,  201) if isPrime(i)] 

注意：在Python 3.x版本中，range() 返回的是一个 range 对象，而不是一个 list（列表），所以你需要把

for i in [2] + range(3, int(sqrt(num)), 2):

改成

for i in [2] + list(range(3, int(sqrt(num)), 2)):

以避免出现 TypeError 错误。

Answer 2

有两点需要注意：

(1) 你一开始不需要把liste设置为[2]；因为你的primeCandidate循环已经包含了2，如果这样做的话，2会被计算两次。

(2) 你的“if isPrime”这一层次有点深了。只有在检查完候选的除数后，你才能相信isPrime的结果。（其实你检查的内容比需要的多，但这只是效率问题，不算是错误。）具体来说：

liste = []
for primeCandidate in range (2,100):
    isPrime = True
    for divisor in range (2,primeCandidate):
        if primeCandidate % divisor == 0:
            isPrime = False
            break
    if isPrime:
        liste.append(primeCandidate)
        print(liste)