SICP Exercise 1.21

Question

Use the smallest-divisor procedure to find the smallest divisor of each of the following numbers: 199, 1999, 19999.

Answer

Let us remember how the smallest-divisor procedure works in detail. The procedure starts counting up all integers from 2 to the first integer that is larger than the square root of \(n\) and checks if \(n\) is divisible by it (i.e. if the modulo is 0). This is like a brute-forcing method for determining the smallest divisor. So, let us see how it works for the three numbers given in the question.

199:

199 % 2 = 1
199 % 3 = 1
199 % 4 = 3
...
199 % 15 = 4

The modulo is never equal to 0. Therefore, 199 is a prime number.

1999:

1999 % 2 = 1
1999 % 3 = 1
1999 % 4 = 3
...
1999 % 45 = 19

Looks like 1999 is another prime number.

19999:

19999 % 2 = 1
19999 % 3 = 1
19999 % 4 = 3
19999 % 5 = 4
19999 % 6 = 1
19999 % 7 = 0

19999 is divisible by 7 because the modulo is equal to 0.