0

誰かがこの素ふるいを通して一行ずつ私を案内してくれませんか? 私は独自のふるいを開発しようとしていますが、高速なもののほとんどには、理解できない構文が含まれています (コメントした行など)。これが一種の初心者の質問である場合は申し訳ありません。また、ふるいの書き込みに役立つリンクがあれば、大歓迎です。

def rwh_primes1(n):
    """ Returns  a list of primes < n """
    sieve = [True] * (n/2) # What does the '[True]' mean?
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]: # The same complaint as in line 3, I don't understand the variable 'sieve'
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1) # how is sieve used here - it seems to be as a list but i'm unsure
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]] # 'sieve' is confusing me here yet again.
4

2 に答える 2

4

コードの各行の意味を斜体で示し、コメントを通常のフォントで追加します。

sieve = [True] * (n/2)

新しいローカル変数sieveを宣言し、値に初期化します[True] * (n/2)。その表現はどういう意味ですか？[True]ブール値のみを含む単一要素のリストですTrue。リストに数値を掛けるとリストが繰り返されるためsieve、すべての値のn/2要素リストになりTrueます。

for i in xrange(3, int(n**0.5)+1, 2):

3 から開始し、sqrt(n) で終了するように、2 ずつカウントを開始します。この特定の範囲の選択は、Sieve アルゴリズムの最適化です。1 から n まで 1 ずつ数えることはできますが、効率は悪くなります。

if sieve[i/2]:

i/2リストのth 要素を見てくださいsieve。の場合は、分岐Trueを下っていきます。if作成者はi/2、コードが 2 のステップでカウントされているという事実を補うために を使用しています。このようにして、より短いリストで作業し、より少ないメモリを使用できます。

sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)

i*i/2 から始まるsievetoのすべての i 番目の要素を更新します。False sieve[i*i/2::i]はスライス表記と呼ばれます- 割り当ての左側に表示されるため、このコードはのそのスライスを更新sieveします。右側は、list-times-number トリックの繰り返しです。False正しい長さのall-list を計算します。

return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

このコードはTrue/のFalse値sieveを素数のリストに変換するだけです。この計算では、各値のインデックスに 2sieveを掛けることで、偶数が含まれていないという事実を補正しています。True

于 2016-03-01T23:43:02.027 に答える