Exercise 1.21 asks us to use the
smallest-divisorprocedure to find the smallest divisor of each of the following numbers: 199, 1999, 19999.
smallest-divisorprocedure 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
squareprocedure 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))
smallest-divisorprocedure 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)
> (smallest-divisor 1999)
> (smallest-divisor 19999)
As you can see, the first two numbers are prime because they are their own smallest divisor, but the third is divisible by 7.
For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.