0

I wanted to find out the nearest prime number (that is present in that array), to any another number in the array ?
Example :

list a -> [1,2,4,6,8,12,9,5,0,15,7]

So the nearest prime number to 4 would be 2 and in case of 15 it would be 7. Here i am assuming that every element in the list is distinct.
I spent hours on it but couldn't solve, is there any efficient way to solve this problem ?

thefourtheye
  • 233,700
  • 52
  • 457
  • 497
user2444327
  • 83
  • 9
  • What's the largest possible number in the list? – John Zwinck Oct 04 '14 at 06:29
  • Define efficient . . . and the approach probably depends on how many numbers we're talking about and how big they can be . . . – mgilson Oct 04 '14 at 06:30
  • define nearest - can the prime value be greater or less than the number given (or even equal to ?). In your example what is the nearest prime to 12 - is it 7 or 15? – Tony Suffolk 66 Oct 04 '14 at 06:51
  • 1
    @TonySuffolk66 -- `15` isn't prime, If I understand the question, I think the "closest" prime to `12` is `5` . . . – mgilson Oct 04 '14 at 06:54
  • doh ! of course 15 isn't prime - doh ! Still needs a clear definition of nearest - nearest in absolute value - nearest in terms of distance in the original list or an other interpretation ? – Tony Suffolk 66 Oct 04 '14 at 06:57

2 Answers2

2

First, you need a good prime number checker. Wikipedia has an implementation -- It could probably be optimized a bit further depending on python version, etc.

Now, make a list of the indices of all prime numbers:

indices = [i for i, val in enumerate(data) if is_prime(val)]

Next, pick an arbitrary number and find it's index (or not arbitrary ...).

n = random.choice(data)
idx = data.index(n)

we're almost there ... bisect your way to figure out where the index of n fits in the indices list.

indices_idx = bisect.bisect_left(indices, idx)

Now, to figure out whether the closer number is on the left or the right we need to look at the values.

# Some additional error handling needs to happen here to make sure that the index
# actually exists, but this'll work for stuff in the center of the list...
prime_idx_left = indices[indices_idx - 1]
prime_idx_right = indices[indices_idx]

and finally, figure out which index is closer and pull out the value:

if (idx - prime_idx_left) <= (prime_idx_right - idx):
    closest_prime = data[prime_idx_left]
else:
    closest_prime = data[prime_idx_right]

Note I cooked this up under the assumption that you'll be using the same list over and over. If you're not, you'd do better to just:

  • find the index of the number you're interested in.
  • find the index of the first prime to the right (if it exists)
  • find the index of the first prime to the left (if it exists)
  • Check which one is closer

e.g.

def find_idx_of_prime(lst, start_idx, stop_idx, dir):
    for ix in xrange(start_idx, stop_idx, dir):
        if is_prime(lst[ix]):
            return ix
    return dir*float('inf')

idx = data.index(number)
left_idx = find_idx_of_prime(data, idx, 0, -1)
right_idx = find_idx_of_prime(data, idx, len(data), 1)
prime_idx = left_idx if idx - left_idx < right_idx - idx else right_idx
prime_value = data[prime_idx]  # raises TypeError if no primes are in the list.
mgilson
  • 300,191
  • 65
  • 633
  • 696
  • 1
    +1. You could find `max(lst)` and use Sieve of Eratosthenes to generate a set of all primes that are less than `max(lst) + 1` then `isprime = primes.__contains__`. [The code is very simple e.g., `sieve_of_eratosthenes(limit)`](http://stackoverflow.com/a/20782064/4279) If `max(lst)` may be large compared to `len(lst)` then a direct primality test could be used such as [you've linked](http://en.wikipedia.org/wiki/Primality_test#Python_implementation). If `max(lst)` is very large then probabolistic method such as Miller–Rabin primality test should be used. – jfs Oct 04 '14 at 11:38
1

Below is a fairly efficient implementation of the Sieve of Eratosthenes that could be used in conjunction with mgilson's code. But as J.F. Sebastian says, using a pre-computed table of primes may not be efficient if the numbers in your list are very large, &/or if the length of the list is small.

def primes(n):
    ''' Return a boolean list of all primes < n '''
    s = [False]*2 + [True]*(n-2)
    for i in xrange(2, int(n**0.5) + 1):
        if s[i]:
            s[i*i : n : i] = [False] * (1 + (n - 1)//i - i)
    return s

You'd use it like this:

a = [1,2,4,6,8,12,9,5,0,15,7]
is_prime = primes(max(a) + 1)

And then change mgilson's find_idx_of_prime() function to:

def find_idx_of_prime(lst, start_idx, stop_idx, dir):
    for ix in xrange(start_idx, stop_idx, dir):
        if is_prime[lst[ix]]:
            return ix
    return dir*float('inf')
PM 2Ring
  • 54,345
  • 6
  • 82
  • 182