Exercise 1.23

Imports: [[Chapter 1.1]] square, [[Exercise 1.22]] search-for-primes

Trial division, but only testing odd divisors:

(define (square x) (* x x))
(define (search-for-primes p? a b) 
  (define (iter a b) 
   (when (<= a b) 
     (timed-prime-test p? a) 
     (iter (+ a 2) b))) 
  (iter (if (odd? a) a (+ a 1)) b))

(define (prime? n)
  (define (divides? a b)
    (= (remainder b a) 0))
  (define (next n)
    (if (= n 2) 3 (+ 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 (smallest-divisor n)
    (find-divisor n 2))
  (= n (smallest-divisor n)))

(string-contains?
 (capture-output (search-for-primes prime? 6 10))
 "7 *** ")
=> #t

Time for 3 primes greater than 1,000:

; 1009 *** 5.1975250244140625e-5   (1.085x)
; 1013 *** 5.1975250244140625e-5   (1.211x)
; 1019 *** 6.198883056640625e-5    (1.294x)

Time for 3 primes greater than 10,000:

; 10007 *** 1.1491775512695312e-4  (1.037x)
; 10009 *** 1.1801719665527344e-4  (1.036x)
; 10037 *** 1.1897087097167969e-4  (0.967x)

Time for 3 primes greater than 100,000:

; 100003 *** 3.540515899658203e-4  (0.883x)
; 100019 *** 3.490447998046875e-4  (0.954x)
; 100043 *** 3.590583801269531e-4  (0.788x)

Time for 3 primes greater than 1,000,000:

; 1000003 *** .0010960102081298828 (0.810x)
; 1000033 *** .001055002212524414  (0.930x)
; 1000037 *** .0010900497436523438 (0.796x)

The expectation of half time was not confirmed. In fact, this method is actually slower for primes under 10,000. Even for seven-figure primes, it only shaves off 20%. There was probably some error in the measure-ments; other processes on the computer and random factors might have played a role. Maybe the overhead of calling next cancels the benefit of skipping even numbers.