¿Cómo encontrar el número primo más cercano en una matriz, a otro número en esa matriz?

Quería averiguar el número primo más cercano (que está presente en esa matriz), a cualquier otro número en la matriz?
Ejemplo:

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

Entonces, el número primo más cercano a 4 sería 2 y en el caso de 15 sería 7 . Aquí estoy asumiendo que cada elemento de la lista es distinto.
Pasé horas en él pero no pude resolverlo, ¿hay alguna forma efficient de resolver este problema?

Related of "¿Cómo encontrar el número primo más cercano en una matriz, a otro número en esa matriz?"

Primero, necesitas un buen comprobador de números primos. Wikipedia tiene una implementación : probablemente podría optimizarse un poco más dependiendo de la versión de Python, etc.

Ahora, haga una lista de los índices de todos los números primos:

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

A continuación, seleccione un número arbitrario y encuentre su índice (o no arbitrario …).

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

casi estamos allí … divisemos su manera de averiguar dónde encaja el índice de n en la lista de índices.

 indices_idx = bisect.bisect_left(indices, idx) 

Ahora, para averiguar si el número más cercano está a la izquierda o a la derecha, necesitamos mirar los valores.

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

y, finalmente, determine qué índice está más cerca y saque el valor:

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

Tenga en cuenta que cociné esto bajo el supuesto de que usará la misma lista una y otra vez. Si no lo eres, harías mejor simplemente:

  • Encuentra el índice del número que te interesa.
  • encontrar el índice de la primera prima a la derecha (si existe)
  • encontrar el índice de la primera prima a la izquierda (si existe)
  • Comprueba cuál está más cerca

p.ej

 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. 

A continuación se muestra una implementación bastante eficiente del Tamiz de Eratóstenes que podría usarse junto con el código de mgilson. Pero como dice JF Sebastian, el uso de una tabla de primos precalculada puede no ser eficiente si los números en su lista son muy grandes, y / o si la longitud de la lista es pequeña.

 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 

Lo usarías así:

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

Y luego cambie la función find_idx_of_prime() de find_idx_of_prime() a:

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