codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
# 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)
Private
[
?
]
Run code
Submit