haskeem-0.6.10: primes.scm

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