计算 python 中的素数

Question

我正在尝试创建一个菜单驱动的程序，该程序将计算并显示 2 和用户输入的限制之间的所有质数。用户可以选择的第一个选项是 "Create a list of primes from 2 to n using the Sieve of Eratosthenes algorithm"。第二个选项是 "Display the prime numbers"，第三个选项是退出。我的代码目前看起来像：

def main():
    choice = displayMenu()
    while choice!= '3':
        if choice == '1':
            sieve()
        elif choice == '2':
            prime
        choice = displayMenu()

    print("Thanks for playing!")
def displayMenu():
    myChoice = '0'
    while myChoice != '1' and myChoice != '2' and myChoice != '3':
        print("""Please choose
                      1. Create a list of primes from 2 to n using
                      the Sieve of Eratosthenes algorithm
                      2. Display the prime numbers
                      3. Quit
                      """)
        myChoice = input("Enter option--->")

        if myChoice != '1' and myChoice != '2' and myChoice != '3':
            print("Invalid option. Please select again.")

    return myChoice

def sieve():
    liste = [ ]
    n = int(input("What number should I go up to?"))
    choice = input("--->")
    for primeCandidate in range (2,n):
        isPrime = True
        for divisor in range (2, primeCandidate):
            if primeCandidate % divisor == 0:
                isPrime = False
                break
            if isPrime:
                liste.append(primeCandidate)
                print(liste)
main()

我发现，当我打印从 2 到 13 的素数时，它打印为

[3]
[3, 5]
[3, 5, 5]
[3, 5, 5, 5]
[3, 5, 5, 5, 7]
[3, 5, 5, 5, 7, 7]
[3, 5, 5, 5, 7, 7, 7]
[3, 5, 5, 5, 7, 7, 7, 7]
[3, 5, 5, 5, 7, 7, 7, 7, 7]
[3, 5, 5, 5, 7, 7, 7, 7, 7, 9]
[3, 5, 5, 5, 7, 7, 7, 7, 7, 9, 11]
[3, 5, 5, 5, 7, 7, 7, 7, 7, 9, 11, 11]
[3, 5, 5, 5, 7, 7, 7, 7, 7, 9, 11, 11, 11]
[3, 5, 5, 5, 7, 7, 7, 7, 7, 9, 11, 11, 11, 11]
[3, 5, 5, 5, 7, 7, 7, 7, 7, 9, 11, 11, 11, 11, 11]
[3, 5, 5, 5, 7, 7, 7, 7, 7, 9, 11, 11, 11, 11, 11, 11]
[3, 5, 5, 5, 7, 7, 7, 7, 7, 9, 11, 11, 11, 11, 11, 11, 11]
[3, 5, 5, 5, 7, 7, 7, 7, 7, 9, 11, 11, 11, 11, 11, 11, 11, 11]
[3, 5, 5, 5, 7, 7, 7, 7, 7, 9, 11, 11, 11, 11, 11, 11, 11, 11, 11]

有没有办法纠正这个问题并且只打印每个质数一次？

Answer 1

您调查过 set 了吗？然后为每个要添加到集合中的新整数执行 set.add?

例如：

In [24]: a=[1]

In [25]: set(a)
Out[25]: {1}

In [26]: b=[1,1]

In [27]: set(b)
Out[27]: {1}

In [28]: c=set(b)

In [29]: c.add(1)

In [30]: c
Out[30]: {1}

In [31]: c.add(2)

In [32]: c
Out[32]: {1, 2}

Answer 2

你的 sieve 函数中的缩进是错误的。这样，您就可以在循环的每次迭代中将主要候选者添加到列表中，并立即打印该列表。相反，您应该仅在测试 all 除数之后添加候选素数，即在内循环之后，并且仅在找到所有素数时才打印数字，即在外循环之后。

试试这个（更改的行已标记）：

def sieve():
    liste = [ ]
    n = int(input("What number should I go up to?"))
    choice = input("--->")
    for primeCandidate in range (2,n):
        isPrime = True
        for divisor in range (2, primeCandidate):
            if primeCandidate % divisor == 0:
                isPrime = False
                break
        if isPrime: # only check isPrime after the loop completed
            liste.append(primeCandidate)
    print(liste)  # only print the list once

此外，如评论中所述，您可能希望将实际算法与用户交互部分分开，并且可以使用更紧凑的 all 函数和生成器表达式而不是内部循环。而且您不必检查 primeCandidate 以内的所有数字；相反，只需检查到目前为止已知的素数。:

def sieve(n): # pass n as parameter
    liste = [ ]
    for primeCandidate in range (2,n):
        # use all with generator, and only check known primes
        isPrime = all(primeCandidate % divisor != 0 for divisor in liste)
        if isPrime:
            liste.append(primeCandidate)
    return liste  # return, don't print

最后注意，严格来说，这是不是一个Sieve of Erastothenes！真实筛子会将 "cross off" 倍数的数字识别为素数，而您的代码使用试除法几乎相反。两者都有效，但除法通常比乘法慢。

有关不同质数算法的广泛讨论，请参阅 this related question。

计算 python 中的素数

Calculating prime numbers in python

python

primes