Dado un número entero N que representa la base de un número, la tarea es encontrar el primo truncable por la izquierda más grande en la base N dada .
Ejemplos:
Entrada: N = 3
Salida: 23
Explicación:
Los números primos truncables por la izquierda en base N(= 3) se dan a continuación:
(12) 3 = (5) 10
(212) 3 = (23) 10
Por lo tanto, los primos truncables por la izquierda más grandes primo en base N(= 3) es (23) 10 .Entrada: N = 5
Salida: 7817
Enfoque: la idea es generar todos los números primos truncables por la izquierda en la base N dada e imprimir el número primo truncable por la izquierda más grande en función de las siguientes observaciones:
Si un número que contiene (i) dígitos es un número primo truncable por la izquierda, entonces los números formados a partir de los últimos (i – 1) dígitos deben ser un número primo truncable por la izquierda.
Por lo tanto, para hacer un número primo truncable por la izquierda de dígitos i , primero encuentre todos los números primos truncables por la izquierda de (i – 1) dígitos.
- Inicialice una array , por ejemplo, candidatas[] , para almacenar todos los números primos truncables a la izquierda posibles en la base N dada .
- Itere sobre el rango [0, infinito] usando la variable i e inserte todos los números primos truncables izquierdos de los dígitos i . Si no se encuentra un número truncable a la izquierda que consta de i dígitos, regrese del bucle.
- Finalmente, imprima el elemento máximo presente en la array candidatas[] .
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python program to implement # the above approach import random # Function to check if a is # a composite number or not # using Miller-Rabin primality test def try_composite(a, d, n, s): # ((a) ^ d) % n equal to 1 if pow(a, d, n) == 1: return False for i in range(s): if pow(a, 2**i * d, n) == n-1: return False return True # Function to check if a number # is prime or not using # Miller-Rabin primality test def is_probable_prime(n, k): # Base Case if n == 0 or n == 1: return False if n == 2: return True if n % 2 == 0: return False s = 0 d = n-1 while True: quotient, remainder = divmod(d, 2) if remainder == 1: break s += 1 d = quotient # Iterate given number of k times for i in range(k): a = random.randrange(2, n) # If a is a composite number if try_composite(a, d, n, s): return False # No base tested showed # n as composite return True # Function to find the largest # left-truncatable prime number def largest_left_truncatable_prime(base): # Stores count of digits # in a number radix = 0 # Stores left-truncatable prime candidates = [0] # Iterate over the range [0, infinity] while True: # Store left-truncatable prime # containing i digits new_candidates = [] # Stores base ^ radix multiplier = base ** radix # Iterate over all possible # value of the given base for i in range(1, base): # Append the i in radix-th digit # in all (i - 1)-th digit # left-truncatable prime for x in candidates: # If a number with i digits # is prime if is_probable_prime( x + i * multiplier, 30): new_candidates.append( x + i * multiplier) # If no left-truncatable prime found # whose digit is radix if len(new_candidates) == 0: return max(candidates) # Update candidates[] to all # left-truncatable prime # whose digit is radix candidates = new_candidates # Update radix radix += 1 # Driver Code if __name__ == "__main__": N = 3 ans = largest_left_truncatable_prime(N) print(ans)
23
Complejidad de tiempo: O(k * log 3 N), donde k son las rondas realizadas en la prueba de primalidad de Miller-Rabin
Espacio auxiliar: O(X) , donde X es el recuento total de números primos truncables por la izquierda en base N
Publicación traducida automáticamente
Artículo escrito por huzaifa0602 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA