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

#### 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.