Matt Bowcock // mbowcock.com

Since I’m working my way through SICP I ended up using some of the code from the examples in section 1.2.6 to search for prime numbers. Six of the eight functions below are used to test if a number is prime. (next-prime …) just starts at the current prime number and iterate upward until it finds the next prime number. (search-for-factors …) does the actual searching for prime factors.

(define (smallest-divisor n)
  (find-divisor n 2))

(define (divides? a b)
  (= (remainder b a) 0))

(define (square n)
  (* n n))

(define (next-divisor n)
  (if (= n 2)
      3
      (+ n 2)))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next-divisor test-divisor)))))

(define (prime? n)
  (= n (smallest-divisor n)))

(define (next-prime n)
  (let ((m (+ n 1)))
    (if (prime? m)
         m
         (next-prime m))))

(define (search-for-factors n factor)
  (cond ((= (/ n factor) 1) (display factor)
                                    (newline))
        ((divides? factor n) (display factor)
                                   (newline)
                                   (search-for-factors (/ n factor) factor))
        (else (search-for-factors n (next-prime factor)))))

(search-for-factors 600851475143 2)