Entry

Sieves / List size hints

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

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

"""
BTW I changed Tim's code back to its original, but added
a test for overflow.

I claim tissieve2 is hard to beat :c)

tissieve1 78498 8.682
tissieve2 78498 4.354
timsieve 78498 6.62

"""

# -------- sieve.py ---------
def tissieve1(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)

def tissieve2(n):
    candidates = range(3, n+1, 2)
    sq = int(n**0.5)
    for p in candidates:
        if p and p<sq: 
          for q in xrange(((p*p)-3)/2, ( (n+1)-3)/2, p):\
            candidates[q] = 0
    return [2] + filter(None, candidates)
    
def timsieve(n):
    if n < 2:
        return []
    candidate = range(n+1)
    primes = [2]
    p = 1
    sq = int(n**0.5)
    while 1:
        p = p + 2
        while p <= n and candidate[p] == 0:
            p = p + 2
        if p > n:
            break
        primes.append(p)
        if p < sq:
          for pmult in xrange(p*p, n+1, 2*p):
            candidate[pmult] = 0
    return primes

def timeit(f):
    from time import clock
    for i in range(1):
        start = clock()
        x = f(1000000)
        finish = clock()
        print f.__name__, len(x), round(finish - start, 3)

timeit(tissieve1)
timeit(tissieve2)
timeit(timsieve)
#---------------------------