Entry

Sieves / List size hints

Jul 5th, 2000 09:59
Nathan Wallace, unknown unknown, Hans Nowak, Snippet 35, Christian Tismer

"""
Packages: basic_datatypes.lists;maths.sieves
"""

"""
Tim Peters wrote:
[many things, also a sieve]

funny, I didn't realize that you wrote
a sieve already. Now I don't want to drop mine.

Here it is, just a few ticks faster (5-10%), and it doesn't 
generate an integer overflow.
"""

def tissieve(n):
    candidates = range(3, n+1, 2)
    for p in candidates:
        if not p: continue
        for q in xrange(3*p, n+1, 2*p):
            candidates[(q-3)/2] = 0
    return [2] + filter(None, candidates)

"""
If found it cheaper to build the xrange from 3*p instead
of p*p, but not having to check for overflow.

Anyway, I'm off topic since list appends are not touched :-)

tissieve(10**6) gives 78498 primes in 8.8 secs,
timsieve is nearly there after 9.4 secs.
(Not intending to race on primes :c)
"""