Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 63 lines (46 sloc) 1.474 kb
3c4db60 @cosmin 1.23
authored
1 (define runtime current-inexact-milliseconds)
2 (define (square x) (* x x))
3 (define (divides? a b) (= (remainder b a) 0))
4
5 ;; from 1.22
6
7 (define (smallest-divisor n)
8 (find-divisor n 2))
9
10 (define (prime? n)
11 (= n (smallest-divisor n)))
12
13 (define (timed-prime-test n)
14 (display n)
15 (start-prime-test n (runtime)))
16
17 (define (start-prime-test n start-time)
18 (if (prime? n)
19 (report-prime (- (runtime) start-time))
20 (newline)))
21
22 (define (report-prime elapsed-time)
23 (display " *** ")
24 (display elapsed-time)
25 (newline))
26
27 (define (even? n) (= 0 (remainder n 2)))
28
29 (define (search-for-primes start end)
30 (if (even? start)
31 (search-for-primes (+ start 1) end) ; skip evens
32 (cond ((< start end) (timed-prime-test start)
33 (search-for-primes (+ start 2) end)))))
34
35 ;; new code for 1.23
36
37 (define (next n)
38 (if (= n 2)
39 3
40 (+ n 2)))
41
42 (define (find-divisor n test-divisor)
43 (cond ((> (square test-divisor) n) n)
44 ((divides? test-divisor n) test-divisor)
45 (else (find-divisor n (next test-divisor)))))
46
47 ;; old results
48
49 ; > (search-for-primes 1000000 1000060)
50 ; 1000003 *** 0.140869140625
51 ; 1000033 *** 0.112060546875
52 ; 1000037 *** 0.09716796875
53
54 ;; new results
55
56 ; > (search-for-primes 1000000 1000060)
57 ; 1000003 *** 0.06103515625
58 ; 1000033 *** 0.06005859375
59 ; 1000037 *** 0.06103515625
60
61 ;; the new code is close to 2x faster. This might be due to invoking
62 ;; next being more expensive than directly invoking +
Something went wrong with that request. Please try again.