How do I find the nearest prime number?

algorithm primes
Marty picture Marty · Oct 15, 2009 · Viewed 26.6k times · Source

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

mjv picture mjv · Oct 15, 2009

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)

Related questions

Printing prime numbers from 1 through 100

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97. But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop …

Read More
Which is the fastest algorithm to find prime numbers?

Which is the fastest algorithm to find out prime numbers using C++? I have used sieve's algorithm but I still want it to be faster!

Read More
How to create the most compact mapping n → isprime(n) up to a limit N?

Naturally, for bool isprime(number) there would be a data structure I could query. I define the best algorithm, to be the algorithm that produces a data structure with lowest memory consumption for the range (1, N], where N is a …

Read More