I've tried to implement the algorithm as described on Wikipedia, and for a modest accuracy (say 25), it runs in less than 30 seconds on your entire number range.

Note that I'm using Math::Pari to verify the next prime number. If you don't have it installed, leave it out and do the check in some other way (against your file of primes, for instance).

I also have the GMP library installed, and use that with Math::BigInt. For small numbers (which 91000-93000 are), this may not have a big benefit.

The way I read the algorithm ..., you're looping too much in your middle loop. I believe you're supposed to choose a fixed accuracy k, and then a random set of k bases. You're using *all* numbers less than n as a base, and that is way too strong, especially for very large numbers, for which this algorithm is designed.

Yes, that's pretty much right. Furthermore, for any number less than 341550071728322, if the Miller-Rabin test doesn't return "composite" for any of the bases 2, 3, 5, 7, 11, 13 and 17, then the number in question is proven to be prime. For numbers less than 1373653 it is sufficient to test only for bases 2 and 3. See http://primes.utm.edu/prove/prove2_3.html

For large numbers Math::BigInt's bmodpow (pure perl) function is just way too slow. You'll be wanting to use something like Math::Pari or Math::GMP (as rhesa has suggested).

Cheers,
Rob

I'm not sure I can help with your question. But you do say you are doing this in part to learn Perl, so I'll make a few (kindly meant) comments about your code.

First, always add use strict; use warnings; to your code. They will save you much grief and tearing of hair

Avoid C style for loops. For example replace

with:

Do not use $a and $b as general purpose variables. They are magical and are used in the context of sort.

If I use your version of a For Loop, how do I tell it to iterate two steps instead of one?

JP Bourget (punklrokk) MS Information and Security Rochester Institute of Technology Rochester, NY

Either use the C style for loop in that case or, if appropriate, do something like for ($start/2..$end/2) with $start and $end both even (but that's rather clunky!).

The Perl style for is very good for iterating over lists so you can do something like for (1.5, 2..4, @moreNumbers). Generally you should think Perl style for first, then C style if you really need it.

---

DWIM is Perl's answer to Gödel

You could do

for (0..(5-1)/2) {  # 1..5, step 2
   my $i = $_*2 + 1;
   ...
}
[download]

but you're probably better off falling back to a C-style loop in that case.

As an aside, the above trick is particularly useful when dealing with floats.

>perl -le "for (my $i=0; $i<10; $i+=0.1) { print $i }"
...
8.79999999999998
8.89999999999998
8.99999999999998
9.09999999999998
9.19999999999998
9.29999999999998
9.39999999999998
9.49999999999998
9.59999999999998
9.69999999999998
9.79999999999998
9.89999999999998
9.99999999999998

>perl -le "for (0..99) { my $i = $_ / 10; print $i }"
...
8.8
8.9
9
9.1
9.2
9.3
9.4
9.5
9.6
9.7
9.8
9.9
[download]

ForgotPasswordAgain,
This advice reeks of cargo-cult mantra chanting. If I was doing a linear search on a sorted list, would you need to profile in order to know that a binary search would be faster? Pure algorithm analysis doesn't require machine profiling. Implementation specific details may distort things where it is warranted. Profiling is always a good rule of thumb, but it isn't always necessary. Especially when the algorithm being implemented is well known and studied. Sometimes it is just a matter of discovering you have implemented it incorrectly.

Cheers - L~R