How do I find the nearest prime number?

Question

Is there any nice algorithm to find the nearest prime number to a given real number? I only need to search within the first 100 primes or so.

At present, I've a bunch of prime numbers stored in an array and I'm checking the difference one number at a time (O(n)?).

Answer 1

The simplest approach would be to store the primes in a sorted list and modify your algorithm to do a binary search.

The standard binary search algorithm would return null for a miss, but it should be straight-forward to modify it for your purposes.

Answer 2

You should sort your number in array then you can use binary search. This algorithm is O(log n) performance in worst case.

Answer 3

If you only need to search in the first 100 primes or so, just create a sorted table of those primes, and do a binary search. This will either get you to one prime number, or a spot between two, and you check which of those is closer.

Edit: Given the distribution of primes in that range, you could probably speed things up (a tiny bit) by using an interpolation search -- instead of always starting at the middle of the table, use linear interpolation to guess at a more accurate starting point. The 100th prime number should be somewhere around 250 or so (at a guess -- I haven't checked), so if (for example) you wanted the one closest to 50, you'd start about 1/5th of the way into the array instead of halfway. You can pretty much treat the primes as starting at 1, so just divide the number you want by the largest in your range to get a guess at the starting point.

Answer 4

Rather than a sorted list of primes, given the relatively small range targetted, have an array indexed by all the odd numbers in the range (you know there are no even primes except the special case of 2) and containing the closest prime. Finding the solution becomes O(1) time-wise.

I think the 100th prime is circa 541. an array of 270 [small] ints is all that is needed.

This approach is particularly valid, given the relative high density of primes (in particular relative to odd numbers), in the range below 1,000. (As this affects the size of a binary tree)

Answer 5

The fastest algorithm? Create a lookup table with p[100]=541 elements and return the result for floor(x), with special logic for x on [2,3]. That would be O(1).

Answer 6

Answers so far are rather complicated, given the task in hand. The first hundred primes are all less then 600. I would create an array of size 600 and place in each the value of the nearest prime to that number. Then, given a number to test, I would round it both up and down using the floor and ceil functions to get one or two candidate answers. A simple comparison with the distances to these numbers will give you a very fast answer.

Answer 7

If you want to write an algorithm, A Wikipedia search for prime number led me to another article on the Sieve of Eratosthenes. The algorithm looks a bit simple and I'm thinking a recursive function would suit it well imo. (I could be wrong about that.)

Answer 8

If the array solution isn't a valid solution for you (it is the best one for your scenario), you can try the code below. After the "2 or 3" case, it will check every odd number away from the starting value until it finds a prime.

static int NearestPrime(double original)
{
    int above = (int)Math.Ceiling(original);
    int below = (int)Math.Floor(original);

    if (above <= 2)
    {
        return 2;
    }

    if (below == 2)
    {
        return (original - 2 < 0.5) ? 2 : 3;
    }

    if (below % 2 == 0) below -= 1;
    if (above % 2 == 0) above += 1;

    double diffBelow = double.MaxValue, diffAbove = double.MaxValue;

    for (; ; above += 2, below -= 2)
    {
        if (IsPrime(below))
        {
            diffBelow = original - below;
        }

        if (IsPrime(above))
        {
            diffAbove = above - original;
        }

        if (diffAbove != double.MaxValue || diffBelow != double.MaxValue)
        {
            break;
        }
    }

    //edit to your liking for midpoint cases (4.0, 6.0, 9.0, etc)
    return (int) (diffAbove < diffBelow ? above : below);
}

static bool IsPrime(int p)  //intentionally incomplete due to checks in NearestPrime
{
    for (int i = 3; i < Math.Sqrt(p); i += 2)
    {
        if (p % i == 0)
            return false;
    }

    return true;
}

Answer 9

Lookup table whit size of 100 bytes; (unsigned chars) Round real number and use lookup table.