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:

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

Post a Comment