如何在數組中找到最接近的素數到該數組中的另一個數？

Question

我想找出最接近的素數（即存在於該數組中），到數組中的任何其他數字？
例子：

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

所以最近的素數到4會2並在15情況下，這將是7。這裏我假設列表中的每個元素都是不同的。
我花了幾個小時就可以解決，但解決不了，有沒有efficient的方法來解決這個問題？

Answer 1

首先，你需要一個好的質數檢查器。 Wikipedia has an implementation - 這很可能是一個有點進一步優化取決於Python版本，等等。現在

，使所有的素數的指數列表：

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

下一步，選擇任意的號碼，找到它是索引（或不是任意的...）。

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

我們快到了......平分你的方式來找出其中的n指數在指數列表相符。

indices_idx = bisect.bisect_left(indices, idx) 

現在，要弄清楚左邊還是右邊的數字是近似的，我們需要看看這些數值。

# 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] 

最後，找出哪些指標更接近，並拉出值：

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

注意我，你會被反覆使用同一列表的假設下熟這件事。如果你沒有，你會做的更好，只是：

• 找到你感興趣的個數指標
• 找到的第一個主要的指數權（如果存在的話）。
• 找到的第一個主要的指標向左（如果存在的話）
• 檢查哪一個更接近

如

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. 

Answer 2

下面是Eratosthenes篩的一個相當有效的實現，它可以與mgilson的代碼結合使用。但正如J.F.塞巴斯蒂安所說，如果列表中的數字非常大，使用預先計算的素數表格可能效率不高，& /或列表長度很小。

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 

你會使用這樣的：

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

，然後更改mgilson的find_idx_of_prime()功能：

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')