Primo Raíz Cuadrada

Problema: Dado un número n, se desea averiguar si este es primo o no.

Ejemplos:

1. Si n = 64. Salida = El número 64 no es Primo.

2. 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

Uri: Prime Number, Super Primes: Engage!