[plt-scheme] fast primality testing

There's a couple examples of this sort of thing in SICP
(http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%25_sec_1.2.6
); they have an exact algorithm and a probabilistic algorithm.  The
probabilistic algorithm is the one you want, and it's really simple. 
Certainly good enough for 17 digits in a flash.

Will

On 7/6/05, Jacob Matthews <jacobm at cs.uchicago.edu> wrote:
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> 
> Schemathics looks like it's got something:
> 
> http://schematics.sourceforge.net/schemathics.html
> 
> Specifically, it looks as though primes.ss (a part of that library)
> has got what you want:
> 
> http://cvs.sourceforge.net/viewcvs.py/schematics/schemathics/
> primes.ss?rev=1.2&view=log
> 
> I can't vouch for whether this file or Schemathics in general works
> in recent versions of DrScheme, though.
> 
> -jacob
> 
> 
> 
> On Jul 6, 2005, at 10:19 PM, Joshua Zucker wrote:
> 
> >   For list-related administrative tasks:
> >   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> >
> > 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.
> >
> > Thanks,
> > --Joshua Zucker
> >
> >
> >
> 
>