in reply to Finding the next larger prime.

If you mean by algorithm "a formula where you put in a prime, and it returns the next prime", then there is no such formula. If you had such a formula, you could make a series that generated all primes, and no such series is known to exist. Such a formula would also solve the twin prime conjecture.

Abigail

Replies are listed 'Best First'.
Re: Re: Finding the next larger prime.
by BrowserUk (Patriarch) on Oct 30, 2003 at 02:05 UTC

    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!

Re: Re: Finding the next larger prime.
by pg (Canon) on Oct 30, 2003 at 20:16 UTC

    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.