; $Id: primes.scm,v 1.2 2008/02/10 06:32:20 uwe Exp $
; Play with prime numbers
; Define an initial set of the lowest couple of primes; only (2 3) is
; strictly necessary, but those two are: the (grow-primes-table)
; routine steps by 2, and that would fail if we had just (2) as the
; initial primes table
(define primes '(2 3 5 7))
; Check a number for primality. This is kinda cute, in that I'm using
; the exception-handling mechanism to simplify the testing: I could
; have a complicated test to determine if I can exit the do-loop, and
; then another test to determine what the value should be, but that's
; a mess. This is much cleaner.
(define (is-prime? n)
(guard (err ((boolean? err) err))
(do ((pl primes (cdr pl))
(cur 0))
((null? pl) (raise "exhausted primes list!"))
(set! cur (car pl))
(when (= cur n) (raise #t))
(when (zero? (remainder n cur)) (raise #f))
(when (> (* cur cur) n) (raise #t)))))
; This computes the next prime past the end of the table and adds it
; to the table, until the size of the primes table is at least n.
(define (grow-primes-table n)
(do ((j (length primes) (+ j 1)))
((>= (length primes) n) primes)
(do ((i (+ 2 (last primes)) (+ 2 i)))
((is-prime? i) (set! primes (append primes (list i)))))))
; This computes the sum of the reciprocals of the first n primes.
; It makes use of the fact that the (gro-primes-table) routine above
; returns the list of primes after it has finished growing it.
(define (sum-recprimes n)
(apply + (map / (list-head (grow-primes-table n) n))))