Dado un número entero positivo, comprueba si el número es primo o no. Un primo es un número natural mayor que 1 que no tiene más divisores positivos que 1 y él mismo. Ejemplos de los primeros números primos son {2, 3, 5, …} Ejemplos: Entrada: n = 11 Salida: verdadero Entrada: n = 15 … Continue reading «Prueba de primalidad | Conjunto 1 (Introducción y Método Escolar)»
Hay varias pruebas de primalidad disponibles para verificar si el número es primo o no, como el teorema de Fermat , la prueba de primalidad de Miller-Rabin y muchas más. Pero el problema con todos ellos es que todos son de naturaleza probabilística. Entonces, aquí viene otro método, es decir, la prueba de primalidad AKS … Continue reading «Prueba de primalidad AKS»
Dado un rango [l, r], la tarea es encontrar la suma de todos los números primos dentro de ese rango. Ejemplos: Input : l=1 and r=6 Output : 10 Input : l=4 and r=13 Output : 36 Enfoque 1: (Enfoque ingenuo) Iterar el bucle de ‘l’ a ‘r’ y sumar todos los números que son … Continue reading «Suma de todos los números primos en un rango dado»
Dado un número entero N , la tarea es imprimir todos los primos seguros por debajo de N primos seguros . Un primo seguro es un número primo de la forma (2 * p) + 1 donde p también es un primo . Los primeros primos seguros son 5, 7, 11, 23, 47,… Ejemplos: Entrada: … Continue reading «Imprima todos los primos seguros debajo de N»
Un número afortunado es el entero más pequeño m > 1 tal que, para un entero positivo dado n, p n + m es un número primo. Aquí p n es el producto de los n primeros números primos, es decir, factores primos (o primoriales ) de orden n. Por ejemplo : p3 = 2 … Continue reading «Encuentra el n-ésimo número de la suerte»
Dado un número K , la tarea es imprimir los números primos presentes en ese nivel dado que todos los números primos están representados en forma de árbol binario . Ejemplos: Input: K = 3 2 / \ 3 5 /\ / \ 7 11 13 17 Output :7, 11, 13, 17 Explanation: 2 / … Continue reading «Números primos presentes en el nivel K de un árbol binario»
Dado un número n, necesitamos encontrar el producto de todos los números primos entre 1 y n. Ejemplos: Input: 5 Output: 30 Explanation: product of prime numbers between 1 to 5 is 2 * 3 * 5 = 30 Input : 7 Output : 210 Usar la criba de Eratóstenes para encontrar todos los números … Continue reading «Encuentra el producto de números primos entre 1 y n»
Dada una secuencia de Prufer de un árbol, la tarea es imprimir los Nodes con grado primo en este árbol. Ejemplos: Input: arr[] = {4, 1, 3, 4} Output: 1 3 4 Explanation: The tree is: 2—-4—-3—-1—-5 | 6 Hence, the degree of 1, 3 and 4 are 2, 2 and 3 respectively which are … Continue reading «Imprima los Nodes con un grado primo en la secuencia de Prufer dada de un árbol»
Este enfoque se basa en el teorema de Wilson y utiliza el hecho de que el cálculo factorial se puede hacer fácilmente usando DP El teorema de Wilson dice que si un número k es primo, entonces ((k-1)! + 1) % k debe ser 0. A continuación se muestra la implementación de Python del enfoque … Continue reading «Una solución interesante para obtener todos los números primos menores que n»
Dadas las consultas Q y P donde P es un número primo, cada consulta tiene dos números N y R y la tarea es calcular nCr mod p. Restricciones: N <= 106 R <= 106 p is a prime number Ejemplos: Entrada: Q = 2 p = 1000000007 1ra consulta: N = 15, R = 4 … Continue reading «Consultas de nCr%p en complejidad de tiempo O(1)»