`prime?' function does not check if x < 2.

[anonymous]

It seems that (prime? 1 2 random) will cause an infinite loop. See fixed version below (perhaps not the best solution). The only change is at the start of the function: (cond ((< x 2) #f) ((or (= x 2) (= x 3)) #t)

(define (prime? x k (rng random))

(cond ((< x 2)

#f)

((or (= x 2) (= x 3))

#t)

((let-values (((s d) (get-s-d (sub1 x))))

(let loop ((i 0))

(if (>= i k)

#t

(let ((test (mod-exp (add1 (rng (- x 3))) d x)))

(if (or (= test 1) (= test (sub1 x)))

(loop (add1 i))
(let carmichael-test ((r 1)

(ctest (modulo (* test test) x)))

(cond ((>= r s)

#f)

((= ctest 1)

#f)

((= ctest (sub1 x))

(loop (add1 i)))

(else

(carmichael-test (add1 r) (modulo (* ctest ctest) x)))))))))))))