# Ticket #1535 (new enhancement)

Opened 11 years ago

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

Reported by: | anonymous | Owned by: | djhaskin987 |
---|---|---|---|

Priority: | trivial | Milestone: | |

Component: | djhaskin987/miller-rabin.plt | Keywords: | primality exhaustive |

Cc: | Version: | (1 4) | |

Racket Version: |

### Description

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)))))))))))))

**Note:**See TracTickets for help on using tickets.