Sieve Of Sundaram
October 7, 2011
We use n for the maximum prime and m for the half-size list of integers:
(define (sundaram n)
(let* ((m (quotient n 2)) (pv (make-vector (+ m 1) #t)))
(do ((i 1 (+ i 1))) ((< (quotient m 4) i))
(do ((j i (+ j 1))) ((< (quotient (- m i) (+ i i 1)) j))
(vector-set! pv (+ i j (* 2 i j)) #f)))
(let loop ((i 1) (ps (list 2)))
(cond ((= i m) (reverse ps))
((vector-ref pv i) (loop (+ i 1) (cons (+ i i 1) ps)))
(else (loop (+ i 1) ps))))))
We employ two optimizations. Since the condition i + j + 2ij ≤ n implies j < (n−i)/(2i+1), the j loop stops early. Similarly, i can never be more than one-quarter of n, allowing the i loop to stop early.
You can run the program at http://programmingpraxis.codepad.org/O6J0rkDn. Shown there are several other sieves, for comparison. The sieves of Euler and Sundaram are slowest, the simple sieve of Eratosthenes is fastest, and the sieve of Atkin is between. We also show a segmented version of the sieve of Eratosthenes, which is a little bit slower than the simple sieve of Eratosthenes (due to the time spent resetting the sieve from one segment to the next) but has the advantages of using much less space and providing a lower bound other than zero.
Pages: 1 2