Lucky numbers in Python

[Cecil Westerhof]

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
LinkedIn: http://www.linkedin.com/in/cecilwesterhof