Para averiguar si un número es primo o compuesto, se divide por la serie de números primos 2, 3, 5, 7, 11, … hasta llegar a una división cuyo cociente sea igual o menor que el divisor. Si todas las divisiones tienen el resto distinto de cero, el número propuesto es un número primo.
Ejemplo: Vamos a ver si el número 101 es un número primo.
• 101 no es divisible por 2.
• 101 no es divisible por 3.
• 101 no es divisible por 5.
– Si dividimos el número 101 por 7:
– Si dividimos 101 por 11:
→ Entonces:
Basta con dividir el número por los números primos menores que él hasta llegar a un cociente menor que el divisor.
Si ninguna de estas divisiones es exacta, el número es primo.
Si alguna de las divisiones es exacta el número es compuesto y podemos interrumpir el proceso.
4- Criba de Eratóstenes
La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores que un número natural dado n. Se forma una tabla con todos los números naturales comprendidos entre 2 y n, y se van tachando los números que no son primos de la siguiente manera: Comenzando por el 2, se tachan todos sus múltiplos; comenzando de nuevo, cuando se encuentra un número entero que no ha sido tachado, ese número es declarado primo, y se procede a tachar todos sus múltiplos, así sucesivamente. El proceso termina cuando el cuadrado del mayor número confirmado como primo es mayor que n.
A continuación, se presentan los pasos que se deben seguir para encontrar los números primos en la criba de Eratóstenes.
Paso 1: Tacha el número 1 con una cruz , ya que este no es ni primo ni compuesto. Luego, encierra en un círculo los números 2, 3, 5 y 7 cada uno con diferente color como se muestra en la tabla.
Paso 2: Tacha con azul todos los múltiplos de 2.
Paso 3: Tacha con rojo todos los múltiplos de 3.
Paso 4: Tacha con verde todos los múltiplos de 5.
Paso 5: Tacha con amarillo todos los múltiplos de 7.
Paso 6: Los números que no se han tachado son los números primos.
Entonces, los primeros números primos son: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 y 97.
