Code

#lang racket

(require "common.scm")

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

(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 (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (remainder (- n 1) 4294967087)))))

(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))

(define (prime? n)
  (= n (smallest-divisor n)))

(define (timed-prime-test n)
  (start-prime-test n (runtime)))

(define number-of-checks 1000)

(define (start-prime-test n start-time)
  (if (fast-prime? n number-of-checks)
      (report-prime n (- (runtime) start-time))
      (display "")))

(define (report-prime p elapsed-time)
  (display p)
  (display " *** ")
  (display elapsed-time)
  (newline))

(define (search-for-primes a b) 
  (timed-prime-test a)
  (cond ((< a b) (search-for-primes (+ a 1) b))))

(define (search-for-primes-start n)
  (search-for-primes (+ n 1) (+ n 1000)))

; tests;

;(search-for-primes-start 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)

(timed-prime-test 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000087)
(timed-prime-test 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000489)
(timed-prime-test 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000513)

Output

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000087 *** 2
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000489 *** 1
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000513 *** 1

Length of big numbers may matter.