1.23|

$ cd ~

SICP Exercise 1.23

Exact same as last problem except you remove redundant checks for even numbers.

#lang sicp

(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 (next test-divisor)))))

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

(define (next x)
  (if (= x 2)
      3
      (+ x 2)))

Again, finding the primes:

> (timed-prime-test 1009)
1009***3
> (timed-prime-test 1013)
1013***2
> (timed-prime-test 1019)
1019***2
> (timed-prime-test 10007)
10007***6
> (timed-prime-test 10009)
10009***9
> (timed-prime-test 10037)
10037***7
> (timed-prime-test 100003)
100003***21
> (timed-prime-test 100019)
100019***20
> (timed-prime-test 100043)
100043***20
> (timed-prime-test 1000003)
1000003***63
> (timed-prime-test 1000033)
1000033***63
> (timed-prime-test 1000037)
1000037***63

Removing redundant checks has certainly helped speed up our program. The time taken wasn’t exactly halved. It’s closer to 1.5x times faster. This is due to if checks in the next procedure.