Test de primalidad "Criba de Eratóstenes"

Los números primos son todos los naturales mayores a 1, que solo son divisibles por sí mismo y el 1. Son considerados los entes atómicos de la teoría de números, por tanto cada número natural se expresa de manera única con factores primos. Osea, son las piezas base en que se componen todos los enteros positivos.

La factorización de un número permite conocer todo los divisores primos del número en cuestión. Para ejemplificar se muestra la factorización de n=6:

2 * 3 = 6

para n=60:

2 * 2 * 3 * 5 = 60

pero para 5 solo es:

5 =5

El método tradicional para probar la primalidad de un número consiste en: revisar todos los valores desde 2 hasta raiz cuadrada del número en busca de un divisor de n. Para demostrar este echo, supongamos que n = a * b entonces a y b son divisores de n, pero ambos no pueden ser mayores a la raíz cuadrada pues el producto sería mayor que n, lo cual demuestra que todos los divisores de n se pueden emparejar con un divisor menor o igual a la raíz y otro divisor mayor o igual a la raíz, así solo basta buscar divisores en el rango dicho.

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

Este método tiene una complejidad de $O(2^n)$ por cada ocación que ejecutes el algoritmo.

-- ¿espera espera, pero si acabamos de iterar hasta la raiz del número?

Bueno, pues erroneamente a la hora de calcular complejidades computacionales, se piensa que las operaciones aritméticas en una computadora tienen complejidades constantes $O(1)$, pero analicemos un poco sobre el tema:

Vamos a sumar los números 64 y 32 a partir de la representación binaria de ambos:

1 0 0 0 0 0

0 1 0 0 0 0

y el resultado no es más q la suma consecutiva de los bits de dichos números

1 1 0 0 0 0

Lo que acabamos de ver, es como la computadora computa la operación aritmética de la suma con una complejidad computacional lineal $O(n)$ en la cantidad de bits de los números, y si llevamos esto a la multiplicación, la cosa se pone incluso más seria, pues la complejidad aritmética es ahora $O(n^2)$.

Con estos datos, volvamos al test de primalidad y veamos ahora la complejidad real. Miremos el número como una cadena de bit (cero y unos), donde al final el tamaño de esa cadena es aproximadamente $\log_2n$ (definamos como cantidad de bits del número a la notación $||n||$), entonces necesitamos hacer $\sqrt{2^{||n||}}$, donde la raiz viene de la complejidad inicial y $2^n$ de la cantidad de bits del número o lo que sería lo mismo, la complejidad en cada computo realizado por la computadora. A continuación acomodemos la complejidad y veamosla de la siguiente manera $2^{||n||/2}$. Como puede verse, ya no tenemos una complejidad $O(\sqrt{n})$, esta se transfomó ahora en $O(2^{||n||/2})$ lo que hace a dicho algoritmo tener una complejidad exponencial.

Criba de Eratóstenes

A continuación veamos uno de los métodos más usados para hallar todos los primos desde 2 hasta n conocido como la Criba de Eratóstenes.

El algoritmo Criba permite descartar todos los números hasta n que sean múltiplos de un x, donde x es un números no descartado hasta el momento.

Dado un Array de números hasta 20, donde no se ha descartado ningún número:

Datos iniciales:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Paso 1: descartar los mútiplos de 2

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Paso 2: descartar los múltiplos de 3

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

y retorna como resultado los primos, como los números no descartados del Array.

El primer paso es definir las variables que van a contener los valores:

#define N 10000001
bool criba[N];

Luego el algoritmo de la criba que precalcule los primos:

// precálculo de los números primos en O(n*log(log(n)))
void preCriba(){
  for(int i=2;i*i<=N;i++){
    if(!criba[i]){
      for(int j=i*i;j<=N;j+=i){
        criba[j]=true;
      }
    }
  }
}

Por tanto para saber si un número es primo solo utilizas los datos precalculados:

// test de primalidad utilizando criba en O(1)
bool esPrimo(int n){
  return !criba[n];
}

El algoritmo de la Criba es útil cuando es necesario saber todos los primos en un rango de números y esta operación es repetitiva.

void main(){

  preCriba();

  
  for(int i=10;i<=50;i++){

    //ahora puede saber si un número es primo en O(1)
    if(esPrimo(i)){
      cout<<i<<" es primo\n";
    }else{
      cout<<i<<" no es primo\n";
    }

  }

}

Si te ha sido de ayuda o te ha resultado interesante el artículo, no dudes en decirnoslo en los comentarios.

Keep Calm and Drink Binary Coffee