小于或等于n的质数

Question

这个说明是这样的：

写一个函数 era1()，让用户输入一个数字 n，然后用这个算法打印出所有小于或等于 n 的质数。

算法步骤：

• 先写一个包含从2到你想计算的最大整数N的数字列表。
• 列表中的第一个数字是一个质数，把这个数字放到一个质数列表 B 中。
• 从列表 A 中去掉第一个元素以及它的倍数。
• 如果列表 A 中的第一个数字小于N的平方根，就回到第二步。
• 列表 B 中的数字和列表 A 中剩下的数字都是我们要找的质数。

现在，我写了这个代码：

import math

def primo(num):
    if num < 2:
        return False

    i = 2
    for i in range(2, int(math.sqrt(num) + 1)):
        if (num % i == 0):
            return False

    return True

def main():
    n = input("Introdueix un nombre: ")
    B = range(2, n)
    for i in B:
        if primo(i):
            print i        

main()

def era1():
    n = input("Introdueix un nombre: ")
    A = range(2, n + 1)
    B = [A[0]]

    for i in A:
        if i % 2 == 0:
            A.remove(i)

    if A[0] < math.sqrt(n):
        print B + A

era1()

结果不对，因为如果我去掉一个输入，就会出现错误，我只能输入一次。而且结果也不对，因为 A + B，列表 B 不是主函数的列表，最后的结果只包含不是2的倍数的数字和2。我该怎么做才能只输入一次，然后得到正确的最终结果呢？

Answer 1

在遍历一个列表的时候，如果你试图把里面的某些项目删除，会出现意想不到的结果，因为这会影响到列表的索引。

a = [1,2,3,4,5,6,7,8,9]
for thing in a:
    a.remove(thing)


>>> a
[2, 4, 6, 8]
>>> 

你需要想个其他的方法来实现这个目标，比如可以新建一个列表，把你想保留的项目放进去。

Answer 2

这个算法叫做埃拉托斯特尼筛法。

它是一个简单的算法，用来找出所有小于或等于某个指定整数的质数。这个算法是由古希腊数学家埃拉托斯特尼在公元前3世纪创造的。

为了开发这个算法，我们将按照上面提到的不同步骤进行。

• 首先，我们生成一个从2到你想计算的最大整数N的数字列表。

A = range(2, n + 1)

• 我们使用另一个列表C，因为稍后我们可能会用A来打印初始列表。

• 我们遍历C，处理所有小于N的平方根的数字。

• 我们初始化一个空列表B，每次发现一个质数（也就是列表中的第一个元素）时就把它加进去。
• 我们使用列表推导来过滤掉倍数，使用的条件是：(x%firstElement!=0)。

C= [x for x in C if x%firstElement!=0]

• B是剩下的数字的集合（大于N平方根的质数）和我们已经发现的质数的结合。

你的代码应该看起来像这样：

def era1():
    n = input("Introduce a nombre: ")
    #n=120 #To test the
    A = range(2, n + 1) 
    B, C= [],A
    while C[0]< math.sqrt(n): #Condition
        firstElement= C[0]
        B+= [firstElement] #The first number in the list is a prime number. Write this number a list of primes, B.
        C= [x for x in C if x%firstElement!=0] #We use comprehension List to filter multiplies using
    return B+C #The numbers in the B list and those left in List A are all primes searched.

print era1()

如果n=120，输出结果是：[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]

这张图片展示了这个算法的过程，图片来源。