Un número primo es un número natural que solo es divisible (con resto cero) por si mismo y por . Por ejemplo, el número
no es primo por que se puede dividir entre
,
y
, sin embargo el número
si es primo, ya que solo se puede dividir entre
y si mismo. Veamos el detalle:
4 % 1 = 0 (true) 4 % 2 = 0 (true) 4 % 3 = 1 (false) 4 % 4 = 0 (true)
Como se puede ver, el número no solo es divisible con resto cero entre
y él mismo, también lo es entre
, por lo tanto no es un número primo. Veamos ahora el detalle con el número
:
11 % 1 = 0 (true) 11 % 2 = 1 (false) 11 % 3 = 2 (false) 11 % 4 = 3 (false) 11 % 5 = 1 (false) 11 % 6 = 5 (false) 11 % 7 = 4 (false) 11 % 8 = 3 (false) 11 % 9 = 2 (false) 11 % 10 = 1 (false) 11 % 11 = 0 (true)
En el caso del número si podemos afirmar que es un número primo ya que solo es divisible por
y por él mismo.
Ahora que ya sabemos cómo podemos identificar un número primo solo queda hacer la lógica en un programa C en el que indicaremos como valor para la variable limite la cantidad de números a analizar, para este ejemplo he puesto .
#include <stdio.h> int main(int argc, char **argv) { int i, limite = 1000, primo, j; for (i = 2; i <= limite; i++) { for (j = 2; j < i; j++) { primo = 1; if (i % j == 0) { primo = 0; break; } } if (primo != 0) printf("%d ", i); } return 0; }
Y tras compilarlo, al ejecutarlo nos devuelve lo siguiente:
Para obtener más cantidad de números primos solo hay que modificar el valor de la variable limite.
Un pequeño apunte para dar menos iteraciones (esto puede ser útil para el test de primalidad de números grandes):
* Puedes comprobar antes del bucle si es divisible por 2. Más que nada porque si lo es, te puedes ahorrar dividirlo por todos los pares.
* El bucle lo puedes empezar en 3 (porque el 2 ya lo has comprobado), puedes incrementar j de 2 en 2 y puede terminar en i/2 (porque si un número lo dividimos por su mitad, su cociente es 2, que será el número más pequeño antes de 1 para dar división exacta).
Hay algoritmos que pueden optimizar más esto, pero así te queda bastante rápido 🙂
Un saludo !!