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.

Advertisements

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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: