[Tutor] primes (generator)

[Gregor Lingl]

Karl Pflästerer schrieb:
> On 19 Mrz 2005, glingl at aon.at wrote:
> 
> [Code]
> 
>>Maybe sombody likes...
> 
> 
> I did it ... :
> 
> def sieve (max):
>     max = max + 1
>     border = round(max**0.5)
>     nums = range(0, max)
>     nums[0] = nums[1] = None
>     for p in nums:
>         if p:
>             if p >= border: break 
>             for i in xrange(p+p, max, p):
>                 nums[i] = None
>     return filter(None, nums)
> 

Hi Karl!

The following variation of your sieve, using
extended slice assignment  seems to
be sgnificantly faster. Try it out, if you like.

def sieve (maximum):
     limit = int(maximum**0.5)
     nums = range(maximum+1)
     nums[0] = nums[1] = None
     for p in nums:
         if p:
             if p > limit: break
             nums[p*p:maximum+1:p] = [False]*(1-p+maximum//p)
     return filter(None, nums)

Regards
Gregor


> 
> 
>    Karl