PRIMES.SCM

(define prime?
  (lambda (n)
    (let ((small-primes     (list 2 3 5 7))
      (small-not-primes (list 0 1 4 6 8 9)))
      (cond
       ((< n 0) (prime? (- 0 n)))
       ((is-contained? n small-primes) #t)
       ((is-contained? n small-not-primes) #f)
       ((has-divisor? n (list 2 3 5 7)) #f)
       ((< n (least-useful-divisor-from n 11)) #f)
       (else #t)))))

(define is-contained?
  (lambda (n L)
    (pertains? n L =)))

(define pertains?
  (lambda (n L pred)
    (cond
     ((null? L) #f)
     ((pred n (car L)) #t)
     (else (pertains? n (cdr L) pred)))))

(define has-divisor?
  (lambda (n L)
    (pertains? n L multiple?)))

(define multiple?
  (lambda (n k)
    (= 0 (remainder n k))))

(define least-useful-divisor-from
  (lambda (n k)
    (cond
     ((> (square k) n) n)
     ((multiple? n k) k)
     (else (least-useful-divisor-from n (+ 1 k))))))

(define square
  (lambda (x) (* x x)))