\$ cd ~

# SICP Exercise 1.22

I had a bit of trouble trying to figure out search-for-primes until I realised I can invoke two procedures in a single cond statement.

(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))
(define (square x) (* x x))

(define (prime? n)
(= n (smallest-divisor n)))

(define (timed-prime-test n)
(start-prime-test n (runtime)))

(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (runtime) start-time) n)))

(define (report-prime elapsed-time n)
(display n)
(display "***")
(display elapsed-time)
(newline))

(define (search-for-primes a b)
(if (even? a) (search-for-primes (+ a 1) b)
(cond ((< a b) (timed-prime-test a)
(search-for-primes (+ a 2) b)))))


I altered the program above to only display primes.

Now, to find the 3 smallest primes larger than 1000, 10,000, 100,000 and 1,000,000:

> (search-for-primes 1000 1500)
1009***4
1013***4
1019***4
> (search-for-primes 10000 10500)
10007***10
10009***12
10037***11
> (search-for-primes 100000 100500)
100003***33
100019***33
100043***32
> (search-for-primes 1000000 1000500)
1000003***95
1000033***103
1000037***103


As the procedure has order of growth $$\Theta (\sqrt{n})$$, it is expected that the time taken to calculate primes around 10,000 should take $$\sqrt{10}$$ times the time taken to calculate primes near 1,000.

This result holds true for all the tested ranges. The time taken for 1,000,000 is roughly 3 times as long as time taken for 100,000.