## 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.

Pages: 1 2

### 5 Responses to “Find The Nearest Prime”

1. Paul said

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))
```
2. John Cowan said

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.

3. Zack said

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

4. programmingpraxis said

@Zack: I’m not familiar with Julia. Is `primes` a built-in function? Or part of the standard library? Does Julia provide integer factorization?

5. Paul said

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
```