I do believe that I can one-up this. The easiest way to speed up
primality testing is to only check factors up to the
square root of the number in question. This is a little messy in
Perl, because evaluating a square root inside a
regex can only be done with an (?{}), or
eval block, which are only semi-implemented and aren't even in most versions of Perl. So, we get around this:
perl -e 'print "PRIME" if (1 x (($A = int sqrt($B = shift))+$B-$A)) !~ /^(11{1,$A})\1+$/' xxx
This is ugly, but works like a dream. The quick explanation: Inside the most nested parentheses, $B is set equal to the number we're testing. The return value of that operation is, simply, $B; therefore, we can set $A equal to the closest integer (rounding down) to the square root of $B. We then take THAT result, add $B to it, and subtract it from itself, before feeding it to the x operator.
With me so far? If X is our number,
$A = int(sqrt(X))
$B = X (note: we no longer need B, but it was useful in setting up the x operator)
The regular expression then evaluates on the original number; but it only checks factors up to its square root. The results are the same, the speed is better. Comparative times to Brontosaurus's algorithm:
NOTE: For some reason, a segmentation fault resulted when using very large numbers. That may be due to precompiled limits killing Perl on my system; running it with -w fixes the problem.
SECOND NOTE: Brontosaurus' computer and mine are not the exact same speed; however, my results using his algorithm were comparable to his, within 20% or so. Close enough, considering the difference between them; my system is slower.
time perl -ew { bla bla bla } 243235
real 0m0.019s
user 0m0.010s
sys 0m0.010s
time perl -ew { bla bla bla } 294824
real 0m0.019s
user 0m0.010s
sys 0m0.010s
Infinitely faster. The delay due to the the + quantifier is killed by the upper limit; it's 493 for the first number, instead of 243235. This is important because Perl starts at the highest possible factor and moves toward the lowest. By eliminating about 242,000 potential factors, the script flies right along.
While both algorithms are still impractical, this one is impractical faster.