sicp exercise 1.22

;  Exercise 1.22. Most Lisp implementations include a primitive called runtime that returns an integer
;  that specifies the amount of time the system has been running (measured, for example, in microseconds).
;  The following timed-prime-test procedure, when called with an integer n, prints n and checks to see
;  if n is prime. If n is prime, the procedure prints three asterisks followed by the amount of time
;  used in performing the test.
;    (define (timed-prime-test n)
;       (newline)
;       (display n)
;       (start-prime-test n (runtime)))
;    (define (start-prime-test n start-time)
;       (if (prime? n)
;       (report-prime (- (runtime) start-time))))
;    (define (report-prime elapsed-time)
;       (display " *** ")
;       (display elapsed-time))
;  Using this procedure, write a procedure search-for-primes that checks the primality of consecutive
;  odd integers in a specified range. Use your procedure to find the three smallest primes larger than
;  1000; larger than 10,000; larger than 100,000; larger than 1,000,000. Note the time needed to test
;  each prime.  Since the testing algorithm has order of growth of O(sqrt(n)), you should expect that testing
;  for primes around 10,000 should take about sqrt(10) times as long as testing for primes around 1000.
;  Do your timing data bear this out? How well do the data for 100,000 and 1,000,000 support the sqrt(n)
;  prediction? Is your result compatible with the notion that programs on your machine run in time
;  proportional to the number of steps required for the computation?


(define (runtime) (gettimeofday))
(define (difftime start end) (+ (* (- (car end) (car start)) 100000) (- (cdr end) (cdr start))))

(define (smallest-divisor n)
    (define (square number) (* number number))
    (define (divides? n divisor) (= (remainder n divisor) 0))
    (define (find-divisor n divisor)
        (cond ((> (square divisor) n) n)
              ((divides? n divisor) divisor)
              (else (find-divisor n (+ divisor 1)))))
    (find-divisor n 2))

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

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


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

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

;(timed-prime-test 3)

(define (search-for-primes start end max)
    (define (search-for-primes-impl start count)
        (cond ((> start end) 0)
              ((= count max) 0)
              (else (if (timed-prime-test start)
                             (search-for-primes-impl (+ start 1) (+ count 1))
                             (search-for-primes-impl (+ start 1) count)))))
    (search-for-primes-impl start 0))

(search-for-primes   1000   10000 3)
(search-for-primes  10000  100000 3)
(search-for-primes 100000 1000000 3)