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:
|
[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]
|
|