1

Pythonでプライムシーブを作成しようとしています。

2 から 2000 までのリストを作成することから始めます。チェックを使用してすべての素数を反復処理し、リストから素数の倍数をすべて削除します。

私はまだ素数のループを回避していませんが、数 2 から始めて、その倍数をすべて削除する方法があります。

primes=list(range(2,2001))
p=2

while p<len(primes):
    for x in range (p*p, len(primes), p):
        primes.remove(x)
    print(primes)

[...] 1989, 1991, 1993, 1995, 1997, 1999, 2000]

ご覧のとおり、2000 という数字はまだ残っていますが、そうあるべきではありません。

Traceback (most recent call last):
  File "C:/Users/Are/PycharmProjects/Project Euler/10.py", line 8, in <module>
    primes.remove(x)
ValueError: list.remove(x): x not in list

私の推論の何が問題になっていますか?

私は PyCharm を使用しています。エラー時に x の値を出力する方法はありますか?

4

4 に答える 4

5

リストの長さは 2000 ではありません。2 から始めます。

>>> primes=list(range(2,2001))
>>> print len(primes)
1999

そのため、while ループを実行すると、2000 にはなりません... :)

于 2013-07-01T20:51:06.963 に答える
4

1999 要素のリストを作成します。

>>> len(range(2,2001))
1999

次に、その長さまでループしますrange()が、その長さは含みません:

for x in range (p*p, len(primes), p):

したがってx、1998 年よりも大きくなることはありません。

の代わりにlen(primes)、上限定数を使用します。

limit = 2001
primes=list(range(limit))

# ...

for x in range (p*p, limit, p):

while p<len(primes):次の問題は、 ;でループし続けることです。リストの一部ではない番号を生成するprimesため、2 度目に削除することはできません。例外ハンドラーを使用して例外をキャッチできます。

try:
    primes.remove(x)
except ValueError:
    # already removed
    pass

whileただし、ループ条件を再考する必要がある場合があります。

于 2013-07-01T20:51:18.577 に答える
1

クラッシュ時の x の値は実際には 4 です。最初のループの最後で p をリストの次の値にインクリメントしません。

次に、リストから値を複数回削除しようとしています。(たとえば) 12 を 2 回削除しようとします。2 を反復するときに 1 回、3 を反復するときに 1 回。

最後に、リストから値を削除すると、リストの長さが常に小さくなります。ループを初めて使用すると、リストのサイズが非常に小さくなります。

コードを作り直す:

primes=list(range(2,2001))
p=2

while p<2000:
    for x in range (p*p, 2001, p):
        if x in primes:
            primes.remove(x)
    while 1:
        p = p + 1
        if p in primes or p > 2000:
            break

print primes
于 2013-07-01T20:58:31.310 に答える