Primo Lineal - dambort/algos GitHub Wiki
Problema: Dado un número n, se desea averiguar si este es primo o no.
Ejemplos:
-
Si n = 16. Salida = El número 16 no es Primo.
-
Si n = 19. Salida = El número 19 es Primo.
Idea del algoritmo:
Un número va a ser primo si solo es divisible enteramente por 1 y por si mismo. Aplicando este concepto, vamos a recorrer todos los números en el intervalo [2,n] para verificar si el numero es divisible por alguno de ellos.
Código
Disponible en Enciclopedia Algoritmos C++
Ejemplo de uso
Disponible en primo lineal
Complejidad: O(n)
Problemas en sitios jueces:
omegaUp: Números Primos
Spoj: PRIME1 - Prime Generator