1.22|

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