2

まず第一に、これは宿題です。私は現在、python でエラトステネスのふるいに取り組んでいます。私のプログラムは次のようになります。

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

1 つの問題は、 にのみ追加することiです。iリストから別の要素をポップするたびに、2にリセットする必要があります。

つまり、最初にリストから 2 をポップします。iリストから 2 の倍数をすべて削除するには、徐々に増やしていきます。これの最後はi50 になります。しかし、戻ってリストから 3 をポップしますが、iまだ 50 であるため50*3、リスト内で検索するだけです。

ただし、これを修正しても機能しません。リストにない値を見つけるとすぐに値を見るのをやめるからですi。しかし、それがリストにない可能性もあります。たとえば、2 の倍数を見つけた後、最初の 3 の倍数 (つまり 6) はリストに含まれていませんが、次の (つまり 9) はリストに含まれています。したがって、リストの最大数まですべての倍数を試すまで停止することはできません。 k*ik*(i+1)

于 2013-11-13T04:42:45.910 に答える
1

コメント:

  • よりわかりやすい変数名を使用する必要があります
  • k * i in x ループに入るたびに i を 2 で再起動する必要があります
  • 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 に答える