Entry

Speedy sieves

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

"""
Packages: maths.sieves
"""

"""
yes, it pays off to avoid the insert at all:

tissieve1 78498 8.699
tissieve2 78498 4.365
tissieve3 78498 4.314
tissieve4 78498 4.292
mcfsieve2 78498 6.779
timsieve 78498 6.637
"""

def tissieve4(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
    if 0 in candidates:
        for i in range(candidates.index(0), 0, -1):\
            candidates[i] = candidates[i-1]
        candidates[0] = 2
    else:
        candidates.insert(0, 2)
    return filter(None, candidates)

"""
but this is ugly much code for those nano seconds...
"""