## Find The Nearest Prime

### August 25, 2017

The trick to this exercise is to realize that it’s a problem about binary search rather than a problem about prime numbers. Enumerate the first hundred primes in an array, then perform binary search. Here’s a simple Sieve of Eratosthenes to compute the primes less than *n*:

(define (primes n) (let ((sieve (make-vector n #t)) (ps (list))) (do ((p 2 (+ p 1))) ((= n p)) (when (vector-ref sieve p) (set! ps (cons p ps)) (do ((i (* p p) (+ i p))) ((<= n i)) (vector-set! sieve i #f)))) (list->vector (reverse ps))))

For our application, we need the primes to 541, which is the hundredth prime:

(define ps (primes 542))

Normal binary search fails if the desired item isn’t in the input. We need a version of binary search that finds the nearest item if the requested item isn’t in the array:

(define (bsearch x xs) (let loop ((lo 0) (hi (- (vector-length xs) 1))) (let ((mid (+ lo (quotient (- hi lo) 2)))) (cond ((< hi lo) (if (< (- (vector-ref xs hi) x) (- x (vector-ref xs lo))) (vector-ref xs lo) (vector-ref xs hi))) ((< x (vector-ref xs mid)) (loop lo (- mid 1))) ((< (vector-ref xs mid) x) (loop (+ mid 1) hi)) (else (vector-ref xs mid))))))

Now we binary search the array of primes for the desired value:

(define (find-prime x) (bsearch x ps))

We take the lower number in case of a tie. Here are some examples:

> (find-prime 123.7) 127 > (find-prime 4) 3 > (find-prime 1000) error: out of bounds

You can run the program at https://ideone.com/xPH7v6.

Pages: 1 2

In Python. This function returns the last prime, if x > last prime. bisect_left is from the bisect module.

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.