sacar - numeros primos recursividad python

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

Question

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 suponiendo que cada elemento en la lista es distinto.
Pasé horas en él pero no pude resolverlo, ¿hay alguna manera efficient de resolver este problema?

Answer 1

A continuación se muestra una implementación bastante eficiente de Sieve of Eratosthenes que podría usarse junto con el código de mgilson. Pero, como dice JF Sebastian, el uso de una tabla de primos precalculados 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'')

Answer 2

Primero, necesitas un buen inspector 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, elija un número arbitrario y encuentre su índice (o no arbitrario ...).

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

ya casi llegamos ... bisequeamos tu camino para descubrir dónde encaja el índice de n en la lista de índices.

indices_idx = bisect.bisect_left(indices, idx)

Ahora, para determinar si el número más cercano está a la izquierda o a la derecha, debemos 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, averigüe qué índice está más cerca y extraiga 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 preparé esto bajo el supuesto de que utilizará la misma lista una y otra vez. Si no es así, será mejor que solo:

• encuentre el índice del número que le interesa.
• encuentre el índice del primer primo a la derecha (si existe)
• encuentre el índice del primer primo a la izquierda (si existe)
• Verifica 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.