2012/12/11 Pierpaolo Bernardi <olopie...@gmail.com>: > On Tue, Dec 11, 2012 at 12:01 PM, Jens Axel Søgaard > <jensa...@soegaard.net> wrote: > >> Below 60 there are only 16 numbers not divisible by 2, 3 or 5. >> The number of bytes needed to store primality results for the >> first million numbers will therefore be >> 1000000 * 16/60 * 1/8 ~ 33333.3 >> >> How much space would be reasonable to use in the library? > > Would make sense to have a user-tuneable parameter (with a small > default) for this? > So a prime intensive computation could do (precompute-primes-up-to > (expt 10 9) ).
That would make sense. > What do Mathematica, Maple, etc, do in this case? Here is what Maxima does (line 628 and below): https://github.com/andrejv/maxima/blob/master/src/ifactor.lisp They keep a table of the primes below 10000. Small numbers are simply looked up in the table. Medium numbers are divided into ranges. In each range Miller-Rabin is used with pre-selected moduli. This makes the test deterministic. For large numbers a pseudo test is used. -- Jens Axel Søgaard ____________________ Racket Users list: http://lists.racket-lang.org/users
