; 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)))