[CODE]
(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 (+ test-divisor 1)))))
(define (divides? a b)
(= (remainder b a) 0))
(define (prime? n)
(= n (smallest-divisor n)))
(define (square x) (* x x))
(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (runtime)))
(define (runtime) (current-milliseconds))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))
(define (search-for-primes rangestart)
(define (SFP-iter start-time n)
(newline)
(display n)
(if (prime? n) (report-prime (- (runtime) start-time))
(SFP-iter start-time (+ n 2))))
(if (even? rangestart) (SFP-iter (runtime) (+ rangestart 1))
(SFP-iter (runtime) rangestart)))
[/CODE]
> (search-for-primes 10000)
10001
10003
10005
10007 *** 21
> (search-for-primes 100000)
100001
100003 *** 21
> (search-for-primes 1000000)
1000001
1000003 *** 22
> (search-for-primes 10000000)
10000001
10000003
10000005
10000007
10000009
10000011
10000013
10000015
10000017
10000019 *** 29
> (search-for-primes 100000000)
100000001
100000003
100000005
100000007 *** 44
> (search-for-primes 1000000000)
1000000001
1000000003
1000000005
1000000007 *** 57
> (search-for-primes 10000000000)
10000000001
10000000003
10000000005
10000000007
10000000009
10000000011
10000000013
10000000015
10000000017
10000000019 *** 317
> (search-for-primes 100000000000)
100000000001
100000000003 *** 676
>
10000 : 21 ms
100000 : 21 ms rate : 1
1000000 : 22 ms rate : 1.05
10000000 : 29 ms rate : 1.32
100000000 : 44 ms rate : 1.52
1000000000 : 57 ms rate : 1.30
10000000000 : 317 ms rate : 5.56
100000000000 : 676 ms rate : 2.13
1000000000000 : 2132 ms rate : 3.15
10000000000000 : 6615 ms rate : 3.10
100000000000000 : 21536 ms rate : 3.26
데이터의 크기가 커지면서 수행시간 이 루트10 의 값인 3.16 가 비슷해져감을 알 수 있다.
그나저나 왜 이 알고리즘이 쎄타(루트n) 의 수행시간을 갖는지는 잘 모르겠다.