SICP Exercise 1.21: Smallest Divisor

From SICP section 1.2.6 Example: Testing for Primality

Exercise 1.21 asks us to use the smallest-divisor procedure to find the smallest divisor of each of the following numbers: 199, 1999, 19999.

The smallest-divisor procedure was given earlier in the section.

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

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

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

This procedure makes use of the square procedure that was defined earlier. You'll need to include it if you want to run the code in an interpreter.

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

The smallest-divisor procedure finds the smallest integral divisor (greater than 1) of a given number n in a straightforward way, by testing to see if n is divisible by each integer from 2 to √n. Since the number of steps is between 1 and √n, the order of growth of the algorithm is O(√n).

We can find the solutions to the exercise by simply running the code in an interpreter.

> (smallest-divisor 199)
199
> (smallest-divisor 1999)
1999
> (smallest-divisor 19999)
7

As you can see, the first two numbers are prime because they are their own smallest divisor, but the third is divisible by 7.


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.