sicp exercise 1.23

;  Exercise 1.23. The smallest-divisor procedure shown at the start of this section does lots of needless
;  testing: After it checks to see if the number is divisible by 2 there is no point in checking to see
;  if it is divisible by any larger even numbers. This suggests that the values used for test-divisor
;  should not be 2, 3, 4, 5, 6, ..., but rather 2, 3, 5, 7, 9, .... To implement this change, define a
;  procedure next that returns 3 if its input is equal to 2 and otherwise returns its input plus 2.
;  Modify the smallest divisor procedure to use (next test-divisor) instead of (+ test-divisor 1).
;  With timed-prime-test incorporating this modified version of smallest-divisor, run the test for each of
;  the 12 primes found in exercise 1.22. Since this modification halves the number of test steps,
;  you should expect it to run about twice as fast. Is this expectation confirmed? If not, what is the
;  observed ratio of the speeds of the two algorithms, and how do you explain the fact that it is
;  different from 2?


(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 (next num)(if (even? num) (+ num 1) (+ num 2)))
    (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 (next divisor)))))
    (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)