2

首先，这是家庭作业，我目前正在 python 上研究 Eratosthenes 筛。我的程序看起来像：

x=[]
    for i in range(2,100):
        x.append(i)
primes=[]
i=2

while len(x)!=0:
    k=x[0]
    x.pop(0)
    primes.append(k)
    while k*i in x:
        x.remove(k*i)
        i+=1

print(primes)
print(x)

当我的程序打印“素数”时，我得到：

[2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39,
41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77,
79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99]

为什么列表中有合数？看起来程序应该可以工作

#

编辑了程序，现在看起来：

x=[]
for i in range(2,100):
    x.append(i)
primes=[]



while len(x)!=0:
    i=2
    k=x[0]
    x.pop(0)
    primes.append(k)
    while k*i<=max(x):
        x.remove(k*i)
        i+=1
        if k*i not in x:
            i+=1

print('primes','\n',primes,sep='')
print('x','\n',x,sep='')

仍然无法正常工作，出现错误；“ValueError：list.remove（x）：x不在列表中”

4

3 回答 3

2

一个问题是您只能添加到i. i每次从列表中弹出另一个元素时，都需要重置回 2。

也就是说，首先你从列表中弹出 2。您逐渐增加i以从列表中删除所有 2 的倍数。在这结束时，i将是 50。但是你返回并从列表中弹出 3，i仍然是 50，所以它只50*3在列表中查找。

但是，即使您解决了这个问题，它仍然不起作用，因为i一旦找到不在列表中的值，您就会停止查看值。但也有可能k*i不在列表中，而是在列表k*(i+1)中——例如，在你找到 2 的倍数之后，3 的第一个倍数（即 6）不在列表中，但下一个（即 9）在列表中。所以你不能停下来，直到你尝试每个倍数直到列表最大值。

于 2013-11-13T04:42:45.910 回答
1

评论：

  • 应该使用更具描述性的变量名称
  • 每次进入 x 循环中的 k * i 都需要在 2 处重新启动 i
  • x.pop(0) 对于大 x 很慢
  • x.remove(k * i) 对于大 x 很慢
  • 应该将内部while循环更改为“while k * i < top”并添加“if k * i in x”。最高为 100。

这是一个使用位列表的工作且快速的筛子：http: //stromberg.dnsalias.org/svn/sieve/trunk/

于 2013-11-13T05:20:57.383 回答
1

您应该接受@BrenBarn 的答案，因为它涵盖了重要的内容。但这里还有一些提示：

  • 有一种更简单、更快捷的方法来制作初始x列表。

让 Python 为你做这件事。range()只需像list()这样包装：

MAX_NUM = 100
x = list(range(2, MAX_NUM))

以后会有更多的机会使用MAX_NUM；继续阅读。

  • 在 Python 中，最好使用for循环range()而不是while循环添加到索引变量。

代替：

i = 2
while k*i <= max(x):
    # do stuff with k*i
    i += 1

试试这个：

for i in range(k*2, max(x), k):
    # do stuff with i

Python 内置range()将为您生成一系列值，从 开始，每次k*2相加，最后一个倍数小于. 现在你的循环运行得更快，你避免了一堆乘法。kkmax(x)

  • 有一种更简单的方法，而不是索引x[0]获取k然后使用x.pop()丢弃k来自 的值。x

list.pop()返回弹出的值。所以你可以像这样在一行中做到这一点：

k = x.pop()
  • 你计算max(x)了很多次。但是你已经知道最大的数了x，因为你建x的。在构建x时，您可以将最大的数字保存在一个变量中，并使用该变量而不是max(x)一遍又一遍地查找。好的部分max(x)是它不会检查已提取的数字；例如，当k为 3 时，将删除 99。但是max(x)很贵，所以我认为使用节省的价值总体上是一种胜利。

这就是我保存的原因MAX_NUM。所以你可以这样做：

for i in range(k*2, MAX_NUM, k):
    # do stuff with i
  • 如果你刚开始，你可能不知道 Python 的set()类，但它对这个问题有好处。正如 dstromberg 在他/她的回答中所说，当包含许多值x.remove(some_value)时会很慢。x但是从 a 中删除值set始终是一个非常快速的操作。

您可以像这样构建一个集合：

x = set(range(2, 100))

该集合将包含从 2 到 99 的所有整数值（包括 2 到 99）。

.discard()然后，关于集合的一个巧妙的事情是：您可以使用成员函数（与 a 一起做的另一件便宜的事情）删除成员，而无需检查它们是否在集合中set。

# list solution
if i in my_list:
    my_list.remove(i)

# set solution
my_set.discard(i)

实际上，两者in（在列表中使用）和list.remove()都很昂贵。所以 aset用一个便宜的操作代替了两个昂贵的操作！

一旦你的原始程序进入工作状态，保留一份副本，然后重写它以使用 aset而不是 a list。将最大整数从 100 增加到 10000 并计算两个程序的时间。你应该注意到不同之处。Aset比 a 需要更长list的时间，但随后您在操作（in测试或删除值）上赢得了大笔时间。

  • 但是您可能想知道，“steveha，aset无法被索引，所以x[0]不会工作......我如何找到k？”

我建议简单地使用带有语句的for循环来生成您需要的值。而不是查看或使用，您可以这样做：range()kx[0]k = x.pop()

for k in range(2, MAX_NUM):
    if k not in x:
        continue

set用ain测试非常快，所以这将很快跳过所有非素数。它不像您的原始程序总是准备好下一个素数那样聪明，但总的来说，我认为 aset是这个问题的胜利。

哦，嘿，我们可以使用MAX_NUM另一个时间。

  • 您可能还想“Aset没有，.pop()所以当筛子完成后，我如何获得我的素数列表？”

再简单不过了！

result = list(my_set)  # get a list of values stored in my_set

因此，筛选掉非素数，然后在完成后取出素数列表。

  • 您可能希望使用稍微好一点的变量名。就个人而言，我喜欢简洁的单字母变量，如果它们用于保持在一起的紧凑代码中，所以我会保留i, 但也许x应该是sieve并且k应该是next_prime什么的。

  • 我很高兴看到您了解如何使用该功能的更高级print()功能，但我认为您的打印代码可以更简单。

而不是这个：

print('primes','\n',primes,sep='')

试试这个：

print('primes')
print(primes)

或者也许是这样：

print('primes:\n{}'.format(primes))

使用上述所有建议来计算埃拉托色尼筛的实际程序比建议要短得多！我已经编写并测试了它，但除非您希望我这样做，否则我不会发布它。我的解决方案（不计算print()调用或空行）是 8 行 Python，第一行是：（MAX_NUM = 100 编辑：这是 6 行，但我没有检查是否k在集合中，所以它很慢。检查增加了两行。）

完成后，将原件与修改后的进行比较。你更倾向哪个？一个似乎比另一个更容易理解？

我喜欢 Python 的一件事是，当一个程序有效地使用 Python 的内置特性时，它会变成一个更简单、更漂亮、更容易理解的程序。

祝好运并玩得开心点！

于 2013-11-13T07:17:52.933 回答