This may not be exactly what you want, but it should do the trick.

sub next_prime_iterator {
   my $num = shift;
   do { $num++ } until is_prime($num);
   return $num;
}

sub is_prime {
   my $guess = shift;
   return 1 if $guess == 2;
   return unless $guess > 2 and $guess % 2;

   my $max = 1 + int $guess ** .5;
   for ( my $divisor = 3; $divisor < $max; $divisor += 2 ) {
       return unless $guess % $divisor;
   }
   return 1;
}
[download]

Some minor (possible) improvements:

sub next_prime_iterator {
   my $num = shift(@_);
   return 3   if  $num < 3;
   do { $num += 2 } until is_prime($num);
   return $num;
}

sub is_prime {
   my $guess = shift(@_);

   my $divisor = 3;
   my $quotient;
   while(1) {
       $quotient= $guess / $divisor;
       return 1   if  $quotient < $divisor;
       return 0   if  int($quotient) == $quotient;
       $divisor += 2;
   }
}
[download]

Note that using int($quotient) == $quotient made me worry that this wouldn't always work if $guess is very near the mantissa limit on your machine. But it turns out that Perl's % doesn't do any better there anyway (it does worse):

my $x= 1+~0;
$x *= 2 while $x != $x+1;
$x /= 2;
my $y= $x;
for( 1..5 ) {
    $x++;
    print $x-$y, " ", $x%3, " ", $x/3-int($x/3), "; ";
}
print $/
__END__
1 0 0.75; 2 0 0; 3 2 0.25; 4 2 0.75; 5 1 0;
[download]

So the first numbers (1 2 3 4 5) show that Perl can handle those integers exactly. The second numbers (0 0 2 2 1) don't follow the pattern of 2 0 1 2 0 1 2 0 1 as they should so % is returning invalid results here. The third numbers (0.75 0 0.25 0.75 0) are following the correct pattern (something close to 0.66 0 0.33 0.66 0 0.33) so I trust my int($quotient) == $quotient test.
                - tye

Abigail

I wasn't thinking of a formula as such. What I seem to recall is that there was some way off using knowledge derived from knowing the preceeding prime, to cut down the search space when finding the next.

I guess what comes down to is if I is prime, is there any thing in that knowledge that would help in deciding that I+2 or I+4 or I+6 etc. is or isn't prime? Is there any way of reducing the 3 .. $candidate^.5 range of divisions in order to determine it primacy or lack thereof?

I know there are some "quick" ways of determining "probable primes" eg ... though I'll admit to not understanding the formula I've seen. I thought I saw a method that used the previous known prime to achieve a similar result.

---

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
Hooray!

It is a unproved statement that such a formula would resolve the twin prime conjecture, although it surely sounds like that it increases the hope.

This implication can not be taken as a given, unless it is proved. We are talking about math, so be precise.

Update: You may be interested in reading the recent findings about primality testing being possible in polynomial-time: PRIMES is in P. But for a much more efficient (but probabilistic) algorithm for testing primality, search Google for the Miller-Rabin primality test. AFAIK it's the most commonly used algorithm, and it's a lot better then checking all the possible divisors. Unfortunately, it uses a fair amount of number theory ;)

"Primes is in P" is the Agarwal/Saxena/Kayal paper isn't it? I'm afraid the proof is way beyond me, but does anyone have a perl or (simple) C implementation of their algorithm?

FWIW :), This guy claims to have improved upon the efficiency of the AKS method. I don't doubt the varacity of his claim, I just can't understand enough of the paper to comment one way or the other:). I haven't succeeded in locating any implementations of the algorithm, nor even a decription that I can understand:(.

---

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
Hooray!

Okay. I found what I remembered. It is the Consequence Two of the Prime Number Theorem.

If I interpret this correctly, which is a big IF, then given that you know a prime and its position then the theorum provides a way of calculating a set of bounds within which the next prime will be located which reduces the search area considerably.

There are various refinements which reduce the search space further with the most recent being

In 1986 Te Riele showed there are more than 10180 successive integers x for which pi(x)>Li(x) between 6.62.10³⁷⁰ and 6.69.10³⁷⁰

However, what the hell the number? "6.62.10" is?, raised to any damn power, I haven't a clue :)

<guess type="wild">
6.62.10³⁷⁰ could be 6.62*10³⁷⁰ - multiplication is sometimes written as a dot in the centre of the line, so it could have been a transcribing error
</guess>


davis

It's not easy to juggle a pregnant wife and a troubled child, but somehow I managed to fit in eight hours of TV a day.

Agreed. Once you notice that the digits after the last '.' are always 10, the realisation dawns, but it meant absolutely nothing when I first saw it. It's a very strange way to right exponential numbers.

It could equally as well mean 6 * 62.10³⁷⁰!

---

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
Hooray!

If I interpret this correctly [...] the theorum provides a way of calculating a set of bounds within which the next prime will be located which reduces the search area considerably

Your conclusion is dead wrong but I don't think it is due to a problem of interpretation. (:

You could use the theorem to restrict the search area for the next prime but it would be much more useful to use other techniques to restrict the search area:

1. Assume the next prime after some prime (P) is larger than P. In fact, you should probably start looking at P+2 unless P is 2 (in which case you simply return 3 without performing any calculations).
2. Assume the next prime after P doesn't have a prime between P and it. That is, start looking close to P and stop looking when you find a prime.

That is, if you used the theorem to find the lower bound of where to search, it would return a value quite a bit below P so using the (obvious) lower limit of P will be a much better choice. And finding an upper bound of where to search is of no use since it will be too high to make sense to start looking there and starting on the low end means we know we will find a prime (the one we are looking for) before we get to the upper bound (or else we'd have proved the theorem incorrect).

                - tye

So, what your saying (if I interpret you correctly:), is that despite all of the revisions and improvements made to the Prime Number Theorum, the margin for error for the lower bound for a given prime P will always be greater than the distance between P and P-1?

If so, its a shame none of the reference material I read actually states that minor caveat! Or maybe they did, but not in a way that I understood.

---

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
Hooray!

http://www.mersenne.org/prime.htm

Note: p is required to be prime, but that is not a sufficient condition. At last check there were only 39 known p which generate Mersenne primes, and generally these p are not sequential.

-QM
--
Quantum Mechanics: The dreams stuff is made of