# [Tutor] primes - sieve of odds

Gregor Lingl glingl at aon.at
Mon Mar 21 01:13:34 CET 2005

```Hi Sean!

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 [2] + filter(None, nums)

Perhaps not very elegant. But approximately twice as fast as
the former version.

Best wishes,
Gregor

Sean Perry schrieb:
> Gregor Lingl wrote:
>
>>
>> The following variation of your sieve, using
>> extended slice assignment  seems to
>> be sgnificantly faster. Try it out, if you like.
>>
>
> Here are the numbers:
> Primes 1 - 1,000,000 timing:
>    extendedSliceSieve: 0.708388 seconds
>            listPrimes: 0.998758 seconds
>             karlSieve: 1.703553 seconds
> primeConciseOptimized: 5.133922 seconds
>              setSieve: 7.564576 seconds
>          primeConcise: 1644.683214 seconds --> 27 minutes 24 seconds
>
> if __name__ == '__main__':
>     # setup timers as a list of tuples (name, timeit instance)
>
>     results = []
>     longest = 0
>     for t in timers:
>         result = t[1].timeit(1)
>         longest = max(longest, len(t[0]))
>         results.append((t[0], result))
>
>     results.sort(lambda x, y: cmp(x[1], y[1]))
>
>     print "Primes 1 - 1,000,000 timing:"
>
>     format_str = "%%%ds: %%f seconds" % longest
>     for i in results:
>         print format_str % i
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
>
>

--
Gregor Lingl
Reisnerstrasse 3/19
A-1030 Wien

Telefon: +43 1 713 33 98
Mobil:   +43 664 140 35 27

Autor von "Python für Kids"
Website: python4kids.net
```