[Tutor] primes - sieve of odds
smichr at hotmail.com
Tue Mar 22 18:37:11 CET 2005
I had done the same thing. I also noted that assigning (or inserting)
an element into a list is faster than creating a new list:
l.insert(0,2) is faster than l = +l.
def sieve (maximum):
if maximum < 2: return 
limit = int(maximum**0.5)
nums = range(1,maximum+1,2)
nums = None
for p in nums:
if p > limit: break
nums[(p*p)//2::p] = [False]*(1+(maximum//p- p)//2)
nums = 2
return filter(None, nums)
> Hi Sean!
> Thanks for your measurements.
> In the meantime I did another amendment,
> leaving out the even numbers from the sieve.
> It goes like this:
> def sieve(maximum):
> nums = range(3, maximum+1, 2)
> for p in nums:
> if p:
> if p*p > maximum: break
> start = (p*p-2)//2
> nums[start::p] = [False]*(1+((maximum-3)//2-start)//p)
> return  + filter(None, nums)
> Perhaps not very elegant. But approximately twice as fast as
> the former version.
More information about the Tutor