如何找到一个数组中最接近的素数,在该数组另一个号码? [英] How to find the nearest prime number in an array, to another number in that array?
问题描述
我想找到最近的素数(即该数组present),任何阵列中的另一个号码?
例如:
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屋!