Entry

Sieves

Jul 5th, 2000 09:59
Nathan Wallace, unknown unknown, Hans Nowak, Snippet 40, Tim Hochberg

"""
Packages: maths.sieves;maths.numeric
"""

"""
Here's two more.... tahsieve1 shaves off about 30% of tissieve3 (which, for
the record, has an off by one error which causes it to fail at e.g., n=10).
tahsieve2 is more than twice as fast as tahsive1, but it's sort of
cheating....
"""

def tahsieve1(n):
    candidates = range(3, n+1, 2)
    sq = int(n**0.5)
    end = ((n+1)-3)/2
    for p in candidates:
        if p > sq: break
        if p:
          for q in xrange(((p*p)-3)/2, end, p):\
            candidates[q] = 0
    candidates = filter(None, candidates)
    candidates.insert(0, 2)
    return candidates

from Numeric import *

def tahsieve2(n):
    candidates = arange(3, n+1, 2)
    sq = int(n**0.5)
    end = ((n+1)-3)/2
    for p in candidates[:sq+1]:
        if p:
            candidates[((p*p)-3)/2:end:p] = 0
    candidates = filter(None, candidates)
    candidates.insert(0, 2)
    return candidates