[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/WAgoUQGS    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Feb 10:
; 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)))


Output:
1
78498


Create a new paste based on this one


Comments: