Como Saber Si Un Numero Es Primo C++

¡Hola, futuros programadores! Prepárense para dominar la identificación de números primos en C++. Aquí les dejo una guía práctica para su examen. ¡Vamos a ello!

¿Qué es un Número Primo?

Un número primo es un número entero mayor que 1. Solo es divisible por 1 y por sí mismo. Recuerden: 2, 3, 5, 7, 11 son ejemplos clásicos. El 1 no se considera primo.

Por ejemplo, 4 no es primo porque es divisible por 1, 2 y 4. En cambio, 7 solo es divisible por 1 y 7.

Algoritmo Básico: Iteración y División

Una forma sencilla de verificar si un número *n* es primo es intentar dividirlo por todos los números desde 2 hasta *n*-1. Si alguna división da un resto de 0, entonces *n* no es primo. ¡Es la idea central!

Aquí está el pseudocódigo básico:

Si *n* es menor o igual a 1, no es primo.
Itera desde 2 hasta *n*-1.
Si *n* es divisible por algún número en este rango, no es primo.
Si termina la iteración sin encontrar un divisor, *n* es primo.

Implementación en C++ (Versión Básica)

Veamos cómo se traduce esto a código C++:


bool esPrimoBasico(int n) {
  if (n <= 1) return false;
  for (int i = 2; i < n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}

Este código toma un entero *n* como entrada. Primero, comprueba si *n* es menor o igual a 1. Luego, itera a través de un bucle. Si encuentra un divisor, devuelve `false`. Si no encuentra ninguno, devuelve `true`.

Optimización: Raíz Cuadrada

Podemos optimizar este algoritmo. No necesitamos iterar hasta *n*-1. ¡Basta con iterar hasta la raíz cuadrada de *n*! Si un número tiene un divisor mayor que su raíz cuadrada, también tiene un divisor menor que su raíz cuadrada.

Por ejemplo, si *n* es 36, su raíz cuadrada es 6. Si 36 es divisible por 9 (que es mayor que 6), también es divisible por 4 (que es menor que 6).

Implementación en C++ (Versión Optimizada)

Aquí está el código C++ optimizado:


#include <cmath>

bool esPrimoOptimizado(int n) {
  if (n <= 1) return false;
  for (int i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) return false;
  }
  return true;
}

Observe que hemos incluido la librería `cmath` para usar la función `sqrt()`. El bucle ahora itera hasta la raíz cuadrada de *n*.

Casos Especiales y Consideraciones

Es importante recordar que 2 es el único número primo par. Todos los demás números primos son impares. Podemos usar esta información para optimizar aún más el código, por ejemplo, comprobando primero si el número es 2, y luego iterando solo a través de los números impares (después de comprobar que no es divisible por 2).

Para números muy grandes, existen algoritmos aún más eficientes, como el test de primalidad de Miller-Rabin. Sin embargo, para la mayoría de los casos, el algoritmo de la raíz cuadrada es suficiente.