Saturday, January 30, 2010

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)
> (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.

1 comment:

Kamagra said...

This is very great thing you have shared with us. Now I found enough resources by your tips about this issue, Thank you.