# weima learns to program

my attempt to do the exercises in sicp.

## Saturday, June 28, 2008

### 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)