2 
def primes(n):
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]
    print [2] + [i for i in xrange(3,n,2) if sieve[i]]

 primes(int(raw_input("Please enter an upper limit ")))

問題は 5 行目で発生します。実装[False] * ((n-i*i-1)/(2*i)+1)が機能することはわかっていますが、その理由はわかりません。

4

1 に答える 1

2

スライスに含まれるすべての要素を1 つの要素に置き換えようとしています:

sieve[i*i::2*i] = [False]

それはリストから要素を削除しますが、ストライドを使用していない場合、Python ではスライスをより少ないまたはより多くの要素に置き換えることしかできません (セクションが連続している場合は許可されます)。いずれにせよ、これらすべての要素を右側から同じ数の要素に置き換えて、ふるいのそれらの位置を に設定できるようにする必要がありますFalse。

そのためには、右側のリストを調整して、スライスされたすべての要素を置き換えるのに十分な要素を確保する必要があります。

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

この式は、0 から始まるインデックス システムでスライスがカバーする要素の数を計算します。n - 1は、最高のインデックスから開始インデックスを引いて、影響を受ける要素の数をストライドで割った値に、ストライドに最初の要素が含まれているため 1 を加えたものです。

Python のxrange()オブジェクト ( range()Python 3) は、同じ計算を行い、より長い説明が含まれています。

Else for step > 0, if n values are in the range, the last one is
lo + (n-1)*step, which must be <= hi-1.  Rearranging,
n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives
the proper value.  Since lo < hi in this case, hi-lo-1 >= 0, so
the RHS is non-negative and so truncation is the same as the
floor.
于 2015-02-18T11:18:00.687 に答える