Find The Nearest Prime
August 25, 2017
I’ve seen this problem several times on Stack Overflow and other message boards:
Write a program to find the nearest prime number to a given real number. You may limit the search to the hundred smallest primes.
Your task is to write the program to find the nearest prime number. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
In Python. This function returns the last prime, if x > last prime. bisect_left is from the bisect module.
def closest_prime(x, prs): index = bisect_left(prs, x) return min(prs[max(index-1, 0):index+1], key=lambda p: abs(p-x))I’m glad to see you providing a pragmatic solution. To be even more pragmatic, though, I’d just Google up a list of primes and copy and paste the first hundred of them.
Implementation in Julia. If it doesn’t look right for some reason, let me know and I’ll post a screenshot instead.
global P = primes(1000)[1:100] # first 100 primes
function NearestPrime(x::Int64)
if x > P[end]
return P[end]
else
d = abs(P – x)
return P[indmin(d)]
end
end
Quite a nifty little problem. It would be more of a challenge if the scope of it were larger though. Thanks
@Zack: I’m not familiar with Julia. Is `primes` a built-in function? Or part of the standard library? Does Julia provide integer factorization?
An alternative solution using a lazy prime generator. Generate primes until the distance between the pime and target increases.
def primegen(): yield from (2, 3, 5, 7, 11, 13) ps = primegen() p = ps.next() and ps.next() q, sieve, n = p**2, {}, 13 while True: if n not in sieve: if n < q: yield n else: next, step = q + 2*p, 2*p while next in sieve: next += step sieve[next] = step p = ps.next() q = p**2 else: step = sieve.pop(n) next = n + step while next in sieve: next += step sieve[next] = step n += 2 def closest_prime(x, limit=542): prs = lazyprimegen() last_prime = next(prs) dist = abs(x - last_prime) for prime in prs: d = abs(x - prime) if d >= dist or prime > limit: return last_prime dist, last_prime = d, prime