En este post te voy a mostrar cómo determinar si un número es primo en C.
Para saber si un número es primo, hay que probar si se puede dividir únicamente entre 1 y entre sí mismo.
Lo que tenemos que hacer para determinar si un número es primo (en C) es probar si el número se puede dividir por otros números que no sean el 1 y el propio número.
¿Y a qué nos referimos con “se puede dividir”? se dice que un número se puede dividir cuando el residuo es cero, bueno, hablando de divisiones enteras. Por ejemplo, el 7 no es divisible entre 2, porque al dividirlo el resultado es 3 y sobra 1.
En cambio, el 10 sí es divisible entre 2, porque al dividirlo el resultado es 5 y sobra 0.
Algoritmo para saber si número es primo en C
Pero basta de hablar, veamos un poco de código.
El 0 y el 1 no son primos, eso lo sabemos desde el inicio así que con un simple if
comparamos y regresamos falso o 0.
Después hacemos un ciclo que irá desde 2 hasta el número dividido entre 2. Por ejemplo, si el número que vamos a probar es 10, debemos ir desde 2 hasta 5.
Dentro del ciclo probamos si el número es divisible con el operador módulo (%
), y si es divisible entonces el número no es primo.
En caso de terminar el ciclo normalmente (o sea, que no se rompió desde dentro) entonce se dice que el número sí es primo.
#include <stdio.h>
/*
Números primos en C
@author parzibyte
Visita mi blog para más tutoriales de programación:
https://parzibyte.me/blog
*/
// Prototipo de función
int esPrimo(int numero);
int main(void) {
int numero;
printf("Dime un número: \n");
scanf("%d", &numero);
if (esPrimo(numero)) {
printf("Es primo");
} else {
printf("No es primo");
}
return 0;
}
int esPrimo(int numero) {
if (numero == 0 || numero == 1) return 0;
/*
El número 4 es un caso especial, pues al dividirlo entre
2 el resultado es 2, y el ciclo nunca se cumple, indicando que
el 4 SÍ es primo, pero realmente NO lo es, así que si el número es 4
inmediatamente indicamos que no es primo (regresando 0)
Nota: solo es para el 4, los demás funcionan bien
*/
if (numero == 4) return 0;
for (int x = 2; x < numero / 2; x++) {
// Si es divisible por cualquiera de estos números, no
// es primo
if (numero % x == 0) return 0;
}
// Si no se pudo dividir por ninguno de los de arriba, sí es primo
return 1;
}
Si te fijas, el número 4 (que no es primo) es especial para este algoritmo (pero no para las matemáticas), pues al dividirlo entre 2 el resultado es 2, y el ciclo nunca se hace.
Por ello es que está el if
que dice que si el número es 4 inmediatamente se dice que no es primo. Esto se hace únicamente para este número y este algoritmo.