Dado un número n , escriba una función eficiente para imprimir todos los factores primos de n . Por ejemplo, si el número de entrada es 12, entonces la salida debería ser «2 2 3». Y si el número de entrada es 315, entonces la salida debería ser «3 3 5 7». Primer enfoque: Los … Continue reading «Programa eficiente para imprimir todos los factores primos de un número dado»
Dado un número N, imprima todos los números en el rango de 1 a N que tengan exactamente 3 divisores. Ejemplos: Input : N = 16 Output : 4 9 4 and 9 have exactly three divisors. Divisor Input : N = 49 Output : 4 9 25 49 4, 9, 25 and 49 have … Continue reading «Números con exactamente 3 divisores»
Dado un entero positivo n , y que es compuesto, encuentre un divisor de él. Ejemplo: Input: n = 12; Output: 2 [OR 3 OR 4] Input: n = 187; Output: 11 [OR 17] Método bruto: pruebe todos los números enteros menores que n hasta encontrar un divisor. Improvisación: pruebe todos los números enteros menores que … Continue reading «Algoritmo Rho de Pollard para factorización prima»
Dado un número N, imprime todos los factores primos y sus potencias. Aquí N <= 10^18 Ejemplos: Input : 250 Output : 2 1 5 3 Explanation: The prime factors of 250 are 2 and 5. 2 appears once in the prime factorization of and 5 is thrice in it. Input : 1000000000000000000 Output : … Continue reading «Factores primos de un numero grande»
Dada una array arr[] tal que 1 <= arr[i] <= 10^12, la tarea es encontrar los factores primos de LCM de los elementos de la array. Ejemplos: Input : arr[] = {1, 2, 3, 4, 5, 6, 7, 8} Output : 2 3 5 7 // LCM of n elements is 840 and 840 = … Continue reading «Factores primos de LCM de elementos de array»
En este artículo, estudiamos una forma optimizada de calcular la factorización prima distinta hasta n número natural utilizando la complejidad de tiempo O O(n*log n) con precálculo permitido. Prerrequisitos: Tamiz de Eratóstenes , Factor mínimo primo de números hasta n . Concepto clave: nuestra idea es almacenar el factor primo más pequeño (SPF) para cada … Continue reading «Número de factores primos distintos de los primeros n números naturales»
Dado un número N y un número primo P , la tarea es encontrar la suma de los divisores más grandes de cada número en el rango [1, N] , que no es divisible por P . Ejemplos: Entrada: N = 8, P = 2 Salida: 22 Explicación: Los números están en el rango [1, … Continue reading «Suma del mayor divisor de números hasta N no divisible por el número primo dado P»
Dado un arreglo con N elementos, la tarea es encontrar el conteo de factores de un número X, que es el producto de todos los elementos del arreglo. Ejemplos: Input : 5 5 Output : 3 5 * 5 = 25, the factors of 25 are 1, 5, 25 whose count is 3 Input : … Continue reading «Contar divisores de multiplicación de arrays»
Dada una array arr[] que representa una lista de factores primos de un número dado, la tarea es encontrar el producto de los divisores de ese número. Nota: Dado que el producto puede tener una impresión muy grande, la respuesta es mod 10 9 + 7. Ejemplos: Entrada: arr[] = {2, 2, 3} Salida: 1728 Explicación: … Continue reading «Producto de divisores de un número de una lista dada de sus factores primos»
Dados dos números N y K , la tarea es encontrar el valor mínimo X tal que N < X*K . Ejemplos: Entrada: N = 8, K = 7 Salida: 2 Explicación: Los números menores que K divisibles por N son 1, 2 y 4. Entonces, el valor mínimo de X es 2 tal que … Continue reading «Encuentre el mayor factor de N tal que N/F sea menor que K»