[ create a new paste ] login | about

Link: http://codepad.org/i22jgU9W    [ raw code | output | fork ]

programmingpraxis - Python, pasted on Sep 12:
# sieve of eratosthenes with 2,3,5-wheel

from math import sqrt

def primes(n):
    size = (n - 7) / 2
    limit = (int(sqrt(n)) - 7) / 2
    buf = [True] * (size+1)
    whlptrn = [2, 1, 2, 1, 2, 3, 1, 3]
    ps = [2, 3, 5]
    i, w = 0, 0
    while i < size:
        if buf[i]:
            p = 7 + 2*i
            if i <= limit:
                pa = [p, 2*p, 3*p]
                j, m = (p*p - 7) / 2, w
                while j <= size:
                    buf[j] = False
                    j += pa[whlptrn[m] - 1]
                    m = m+1 if m < 7 else 0
            ps.append(p)
        i += whlptrn[w]
        w = w+1 if w < 7 else 0
    return ps

print primes(100)


Output:
1
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]


Create a new paste based on this one


Comments: