[plt-scheme] Fast primality testing

Hi Joshua,

 > I'm playing around with a problem from Al Zimmerman's Programming Contest,
 >   http://www.recmath.org/contest/description.php
 > not really to try to win the contest, but just to have an excuse to
 > teach myself some more scheme.
 >
 > One part I'm not really interested in teaching myself, though: is
 > there a reasonably fast primality-checker in some library somewhere? No big requirements here: it just has to operate 
to return true or
 > false, pretty fast, for numbers up to 17 digits.

I do it by:

(require (lib "mathematica.ss" "mrmathematica"))
(define (prime? n)
  (MathEval `(PrimeQ ,n)))

"PrimeQ first tests for divisibility using small primes, then uses the Miller©\Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test."

-
Chongkai Zhu