Próximo número primo y palíndromo más alto

¿Hay alguna sugerencia sobre cómo resolver el número primo y palíndromo superior de un int dado?

Aquí está el fragmento que estoy intentando, pero es un poco lento, por favor sugiera si tiene algún buen algoritmo que pueda probar.

#!/usr/bin/python def next_higher(n): while True: s = str(n) if not any([n % i == 0 \ for i in range(2, int(n**0.5))]) and s == s[::-1]: return n n = n + 1 print next_higher(2004) print next_higher(20) 

Salida:

 10201 101 

Prueba de código actualizada para palíndromo antes de cebado mucho más rápido que mi código anterior. Estoy implementando la sugerencia de user2357112.

  #!/usr/bin/python def next_higher(n): while True: s = str(n) if s == s[::-1]: if not any([n % i == 0 \ for i in range(2, int(n**0.5))]): return n n = n + 1 print next_higher(2004111) print next_higher(2004) print next_higher(2004) print next_higher(20) 

    Hay bastantes optimizaciones que podrías hacer:

    • Al igual que user2357 .. sugerido en los comentarios, pruebe primero la palidez del medio, y luego verifique si el número es primo, ya que el chequeo principal es más caro.
    • No es necesario que verifique la divisibilidad de los números pares una vez que verifique si el número es divisible entre 2. Por lo tanto, puede cambiarlo a [2] + range(3, int(n**0.5) + 1, 2) para verificar solo Números impares después de 2. (También necesitas hacer sqrt + 1 como mencioné en los comentarios)
    • Debes usar () lugar de [] . [] genera la lista completa de factores primero y solo luego verifica si hay any . Si usa () , crea un generador, por lo que se detiene tan pronto como se encuentra un valor True sin calcular la lista completa.
    • También debe usar xrange lugar de range por la misma razón ( xrange le da un generador, range le da una lista)
    • Puede usar el algoritmo de Tamiz de Eratóstenes para reducir significativamente el tiempo necesario para verificar el número primo.
    • También puede ver si la comprobación del palíndromo se puede hacer más rápido. En realidad, puedes omitir muchos números en lugar de hacer + 1 cada vez.

    Aquí hay una versión con la mayoría de estas optimizaciones, excepto las dos últimas:

     def next_higher(n): if n % 2 == 0: n = n - 1 while True: n = n + 2 s = str(n) if s == s[::-1]: if not any((n % i == 0 for i in xrange(3, int(n**0.5) + 1, 2))): return n 

    Esto debería ser bastante rápido para sus necesidades, creo. Pero puedes hacer las 2 últimas optimizaciones para que sea mucho más rápido si lo deseas.

    Aparte de lo que ya se ha sugerido,

    Lo que sugiero es que primero obtenga el primer número de palíndromo que sea más alto que el número entero dado.

    Puedes hacer esto intentando hacer coincidir los dígitos del centro hacia afuera.

    Además, solo debe verificar los números con un número impar de dígitos, ya que si un número tiene un número par de dígitos y es un palíndromo, entonces siempre será divisible entre 11 y no puede ser primo.

    Una vez que obtenga el primer número de palíndromo que tenga un número impar de dígitos y que sea más alto que el número actual, pruébelo para determinar su primalidad y encuentre el siguiente número de palíndromo más alto que este.

    Puedes hacer esto incrementando el dígito central.

    Sigue haciendo esto hasta que llegue a cero. En ese caso comienza a incrementar los dos dígitos vecinos.

    Continúa, hasta que scopes un número primo.

    Intenté optimizar la comprobación del palíndromo, es decir, para encontrar palíndromos impares. Dado que el primer dígito debe ser un número impar, me concentré en esa parte. Aquí está el código a continuación con las suposiciones es mayor que 1 dígito.

     def next_odd_palindrome(n): """to check the next odd palindrome number""" if n%2==0: n=n-1 while True: n=n+2 s = str(n) if int(s[0])%2==0: n = int(str(int(s[0])+1)+ s[1:]) s = str(n) if s==s[::-1]: return n 

    Déjame saber si algo está mal.

    Solo por diversión, implementé todas las optimizaciones de Hari Shankar y Abhishek Bansal.

    Primero encuentra el palíndromo de longitud impar más alta, luego incrementa el palíndromo de manera que mantenga su palíndromidad. Luego verifica cada número usando los números primos calculados por el método Sieve al principio.

    Esto puede procesar hasta n=10^14 (puede ser mayor si aumenta el tamaño de CACHE) en 1 segundo en mi computadora = D

     primes = [] CACHE = int(10**7) # Cache size for Sieve # Custom class for immediate printing of output import sys class Unbuf: def __init__(self,stream): self.stream = stream def write(self,data): self.stream.write(data) self.stream.flush() sys.stdout = Unbuf(sys.stdout) def sieve(): global primes is_prime = [False,False]+([True]*(CACHE-1)) for i in xrange(2,int(CACHE**0.5)): if is_prime[i]: is_prime[i*i::i] = [False]*((CACHE-i*i+i)/i) primes = [num for num, bool_prime in enumerate(is_prime) if bool_prime] def is_prime(n): """Checks whether n is prime""" global primes if n<2: return False if n==2: return True for prime in primes: if prime>n**0.5+1: return True if n%prime==0: return False # For the case that the number is bigger than the square of our largest prime for num in xrange(primes[-1]+2,n**0.5+1,2): if n%num==0: return False return True def next_higher_odd_length_palindrome(n): n = str(n) if len(n)%2==0: # Even length, take the smallest odd length (10(00)*1) n = '1'+('0'*(len(n)-1))+'1' else: middle_idx = len(n)/2 left = int(n[:middle_idx+1]) left_cmp = n[middle_idx::-1] right_cmp = n[middle_idx:] # If mirroring left part to right part # makes the number smaller or equal, then if right_cmp>=left_cmp: # Increase the left half number left = left+1 # Mirror left part to the right part n = str(left)+str(left)[-2::-1] return n def next_higher(n): if n<=1: return 2 # Ensure the number is a palindrome of odd length n = next_higher_odd_length_palindrome(n) while True: if is_prime(int(n)): return int(n) n = next_higher_odd_length_palindrome(n) if int(n[0])%2==0: new_lead = str(int(n[0])+1) n = new_lead+n[1:-1]+new_lead import time print 'Sieving...', start_time = time.time() sieve() print 'Done in %.3fs' % (time.time() - start_time) print next_higher(2004111) print next_higher(2004) print next_higher(20) while True: n = int(raw_input('Enter n: ')) start_time = time.time() result = next_higher(n) print 'Next higher prime palindrome: %d (calculated in %.3fs)' % (result, time.time() - start_time) 

    Que en mi computadora da esta salida:

     Tamizado ... Hecho en 1.444s
     3007003
     10301
     101
     Introduzca n: 1999999999
     Siguiente palíndromo primario superior: 10000500001 (calculado en 0.004s)
     Introduzca n: 1999999999999
     Siguiente palíndromo primario superior: 3000002000003 (calculado en 0.051s)
     Introduzca n: 1000000000000
     Siguiente palíndromo primario superior: 1000008000001 (calculado en 0.030s)
     Escribe n: