Primo Raíz Cuadrada - dambort/algos GitHub Wiki
Problema: Dado un número n, se desea averiguar si este es primo o no.
Ejemplos:
-
Si n = 64. Salida = El número 64 no es Primo.
-
Si n = 23. Salida = El número 23 es Primo.
Idea del algoritmo:
Un número va a ser primo si solo es divisible enteramente por 1 y por si mismo. Un método para determinar la primalidad de un número es la división por tentativa, que consiste en dividir sucesivamente ese número entre los números primos menores o iguales a su raíz cuadrada. Aplicando este método, verificaremos que el número dado n no es enteramente divisible por los números en el intervalo [2,√n].
Código
Disponible en Enciclopedia Algoritmos C++
Ejemplo de uso
Disponible en primo raíz cuadrada
Complejidad: O(√n)
Problemas en sitios jueces:
omegaUp: Números Primos
Spoj: PRIME1 - Prime Generator