CODEWITHSUNDEEP
pythonpython-2.7primessieve-algorithm
Aaron
Aaron

Reputation: 175

Looking at a prime sieve program but unsure why it keeps coming up with an error about slice length

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 ")))

The problem occurs on line 5 I know that implementing [False] * ((n-i*i-1)/(2*i)+1) works but I am not sure why.

Upvotes: 2

Views: 57

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1123350

You are trying to replace all elements covered by your slice with one element:

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

That would remove elements from the list, except Python only lets you replace a slice with fewer or more elements if you are not using a stride (it would be allowed if the section was contiguous). Either way, you'd want to replace all those elements with an equal number of elements from the right-hand side, so you can set those positions in the sieve to False.

To that end, you'll need to adjust the list on the right-hand side to have enough elements to replace every sliced element:

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

The formula calculates how many elements the slice covers in a 0-based indexing system; n - 1 is the highest index, minus the starting index to give you a number of elements affected, divided by the stride, plus 1 as the stride includes the first element.

Python's xrange() object (range() in Python 3), makes the same calculation, and includes a longer explanation:

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.

Upvotes: 2

Related Questions