Lucky numbers in Python
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 :
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):
if n < 3:
sieve = range(1, n + 1, 2)
sieve_index = 1
sieve_len = len(sieve)
if (sieve_index + 1) > sieve_len:
skip_count = sieve[sieve_index]
if sieve_len < skip_count:
del sieve[skip_count - 1 : (sieve_len // skip_count) * skip_count : skip_count]
sieve_index += 1
> 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:
So the last element (5) is deleted.
Senior Software Engineer
More information about the Python-list