codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; sieve of atkin (define (atkin limit) (let ((v (make-vector (+ limit 1) #f))) (define (flip k) (vector-set! v k (not (vector-ref v k)))) (do ((x 1 (+ x 1))) ((> (* x x) limit)) (do ((y 1 (+ y 1))) ((> (* y y) limit)) (let* ((n (+ (* 4 x x) (* y y))) (nmod12 (modulo n 12))) (if (and (<= n limit) (member nmod12 '(1 5))) (flip n))) (let* ((n (+ (* 3 x x) (* y y))) (nmod12 (modulo n 12))) (if (and (<= n limit) (= nmod12 7)) (flip n))) (let* ((n (- (* 3 x x) (* y y))) (nmod12 (modulo n 12))) (if (and (> x y) (<= n limit) (= nmod12 11)) (flip n))))) (do ((n 5 (+ n 1))) ((> (* n n) limit)) (if (vector-ref v n) (do ((k (* n n) (+ k (* n n)))) ((> k limit)) (vector-set! v k #f)))) (let ((ps '(3 2))) (do ((n 5 (+ n 1))) ((> n limit) (reverse ps)) (if (vector-ref v n) (set! ps (cons n ps))))))) (display (length (atkin 1000000)))
Private
[
?
]
Run code
Submit