如何在数组中找到与该数组中另一个数最近的素数? [英] How to find the nearest prime number in an array, to another number in that array?

问题描述

我想找出与数组中的任何其他数字最接近的素数(存在于该数组中)?
示例:

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]

所以与 4 最接近的素数是 2 而在 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 ?

推荐答案

首先，您需要一个好的质数检查器.维基百科有一个实现——它可能会根据python版本进一步优化，等

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)

我们就快到了......用你的方式来找出 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:

• 找到您感兴趣的号码的索引.
• 找到右边第一个素数的索引(如果存在)
• 找到左边第一个素数的索引(如果存在)
• 检查哪个更近

例如

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.

这篇关于如何在数组中找到与该数组中另一个数最近的素数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！