| Subject: | is_prime() stop when find divisor |
| Date: | Mon, 29 Aug 2011 08:54:18 +1000 |
| To: | bug-Math-Prime-XS [...] rt.cpan.org |
| From: | Kevin Ryde <user42 [...] zip.com.au> |
It'd be good if is_prime() was a bit faster. It does the full
xs_sieve_primes() up to N does it? It could stop on finding a divisor,
in the style of xs_mod_primes().
I suspect there's some optimizations possible in that xs_mod_primes()
too. Even number trial divisors could be skipped. Could even skip
multiples of 3 too with something like start i=5, trial i and i+2 (which
are 6*k+5 and 6*k+1) then loop i+=6. And of course stop at sqrt(n), no
need to go right up to n.
Does xs_mod_primes() also check all n and then not return those less
than the requested base? Perhaps it could easily just run its outer
loop as "base to number".