Exercise 1.24

Imports: [[Chapter 1.2]] fast-prime?, [[Exercise 1.22]] search-for-primes

(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 (fast-prime? n times) 
  (or (= times 0) 
    (and (fermat-test n) 
    (fast-prime? n (- times 1)))))

(define (prime? n) (fast-prime? n 100))

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

\(A =\) time for 3 primes greater than 1,000.

; 1009 *** .003638029098510742
; 1013 *** .003793001174926758
; 1019 *** .003606081008911133

\(B =\) time for 3 primes greater than 10,000. \((0.988A < B < 1.196A)\)

; 10007 *** .004311084747314453
; 10009 *** .0039730072021484375
; 10037 *** .0037479400634765625

\(C =\) time for 3 primes greater than 100,000. \((0.893B < C < 1.294B)\)

; 100003 *** .004847049713134766
; 100019 *** .004848003387451172
; 100043 *** .003850221633911133

\(D =\) time for 3 primes greater than 1,000,000. \((0.891C < D < 1.453C)\)

; 1000003 *** .005592823028564453
; 1000033 *** .004972934722900391
; 1000037 *** .0043179988861083984

Since the Fermat test has \(\Theta(\log n)\) growth, time to test primes near 1,000,000 is only a bit greater than for primes near 1,000. The tests show this: for each additional order of magnitude of the primes, the time required increases by a small, constant amount. Specifically, primes that are 10 times larger take about 1 millisecond longer. These results may be dependent on the choice of 100 as the second argument to fast-prime?.