# Lucky numbers in Python

Cecil Westerhof Cecil at decebal.nl
Wed Apr 29 23:45:08 CEST 2015

```Op Wednesday 29 Apr 2015 21:57 CEST schreef Ian Kelly:

> On Wed, Apr 29, 2015 at 12:24 PM, Cecil Westerhof <Cecil at decebal.nl> wrote:
>> I was wondering if there is a way to do this:
>> for del_index in range((sieve_len // skip_count) * skip_count - 1,
>> skip_count - 2, -skip_count):
>> del sieve[del_index]
>> in a more efficient way.
>
> You can delete using slices.
>
> del sieve[(sieve_len // skip_count) * skip_count - 1 : skip_count -
> 2 : -skip_count]
>
> Now you no longer need to do the iteration in reverse, which makes
> the slicing simpler:
>
> del sieve[skip_count - 1 : (sieve_len // skip_count) * skip_count :
> skip_count]

I expected that it could be done more efficiently, but did not expect
such a big difference: more as hundred times. The old situation took
20 seconds for 1000000. The new takes 0.17.

The code is know (I added a missing check):
def lucky_numbers(n):
if n < 3:
return [1]
sieve = range(1, n + 1, 2)
sieve_index = 1
while True:
sieve_len   = len(sieve)
if (sieve_index + 1) > sieve_len:
break
skip_count  = sieve[sieve_index]
if sieve_len < skip_count:
break
del sieve[skip_count - 1 : (sieve_len // skip_count) * skip_count : skip_count]
sieve_index += 1
return sieve

> And although it's not clear to me what this is supposed to be doing,
> you probably no longer need the middle term if the intention is to
> continue deleting all the way to the end of the list (if it is then
> I think you have a bug in the existing implementation, since the
> last item in the list can never be deleted).

What do you mean by this? Executing:
lucky_numbers(5)
gives:
[1, 3]

So the last element (5) is deleted.

--
Cecil Westerhof
Senior Software Engineer