Many implementations of Sieve of Eratosthenes (used to find prime numbers up to a given n) use a temporary mutable array to keep track of which numbers are composites. I'm looking to write a purely functional version that has the same runtime complexity:
(define (primes-up-to n) (cons 2 (unfold null? car (compose remove-odd-multiples car+cdr) (iota (quotient (- n 1) 2) 3 2)))) (define (remove-odd-multiples n xs) (let recur ((xs xs) (i (* n n))) (cond ((null? xs) '()) ((< (car xs) i) (cons (car xs) (recur (cdr xs) i))) ((< i (car xs)) (recur xs (+ i n n))) (else (recur (cdr xs) (+ i n n))))))
(Should work on any Scheme implementation that supports SRFI 1. If your implementation doesn't provide
(lambda (x) (remove-multiples (car x) (cdr x))) instead.)
What I'm hoping reviewers can help with: Is there a way to make
remove-odd-multiples¹ less verbose (perhaps using higher order functions) or more efficient², without increasing the runtime complexity (so any kind of
remove involving non-constant-time predicates is no go)?
xs does not contain even numbers, there's no point dropping even multiples, hence
remove-odd-multiples. The only difference from a more general
remove-multiples is that it advances
2n instead of
n each time.
² I've done some casual timing tests on
(primes-up-to 100000) on DrRacket 6.5 and the right-folding version you see above is faster than a left-folding version. (I mention this preemptively because many Scheme answerers on Stack Overflow lean towards left-folding solutions.) Here's the left-folding version I time-tested with:
(define (primes-up-to n) (reverse (unfold-right null? car (compose remove-odd-multiples car+cdr) (iota (quotient (- n 1) 2) 3 2) '(2)))) (define (remove-odd-multiples n xs) (let loop ((result '()) (xs xs) (i (* n n))) (cond ((null? xs) (reverse result)) ((< (car xs) i) (loop (cons (car xs) result) (cdr xs) i)) ((< i (car xs)) (loop result xs (+ i n n))) (else (loop result (cdr xs) (+ i n n))))))