El interesante mundo de los números primos


La Teoría de Números es una rama de las Matemáticas que se encarga de estudiar las propiedades de los números, especialmente los números enteros. Sin dudas, los números primos fueron uno de los elementos más estudiados por los matemáticos de la antigüedad, ¿cómo están distribuidos?, ¿son un conjunto infinito?, todo esto fue fruto de polémica e investigación. En el presente artículo te doy una panorámica de esta interesante rama de la Matemática

¿Qué son los números primos?

Se define al conjunto de los números primos como todos los números naturales mayores que 1 que tengan como únicos divisores al 1 y a él mismo.

Cabe señalar que existe polémica sobre considerar al 1 como un número primo, pero los matemáticos de la actualidad han decidido no considerarlo así.

Los números mayores que 1 que no sean primos se denominan números compuestos.

Criba de Eratosthenes:

La manera más eficiente de encontrar los números primos fue creada por el matemático griego Eratosthenes. El algoritmo se basa en crear un arreglo de números positivos no mayor que un entero MAX y va marcando los múltiplos de los primos menores o iguales que la raíz de MAX. Los números que queden sin marcar son los primos, y los marcados son los compuestos.

Criba de Eratosthenes.

Criba de Eratosthenes.

Encontrar números primos en C++

#define MAX 10000
bool prime[MAX];
void sieve()
{   /*
    inicializa en true el arreglo, esto significa que al 
    inicio todos los numeros se consideran primos.
    */
    memset(prime, true, sizeof(prime));
    //el 0 y el 1 por claridad lo ponemos en false ya que no son primos
    prime[0] = prime[1] = false;

    for(int i = 2; i * i <= MAX; i++)
    {
        /*
        Cada vez que nos movamos hacia adelante, comprobamos que la posición 
        en que estemos sea true, esto quiere decir que ese número es primo, 
        por lo que tachamos todos los números que sean múltiplos de este
        nuevo primo.
        */
        if(prime[i])
        {
            for(int j = i+i; j<= MAX; j+=i)
            {
                prime[j] = false;//tachamos todos los multiplos de i
            }
        }
    }
}
//al final del algoritmo si prime[j] = true significa que j es un número primo

Alguna de las aplicaciones que podemos darle a los números primos es la factorización de números, esto es una poderosa herramienta. Si conocemos todos los factores primos de un número, podemos determinar la cantidad de divisores de este.

Sean p1,p2,...pk los factores primos sin repetirse de un número n.

CantDiv(n) = (a1 + 1)*(a2 + 1)*.....*(ak + 1) donde ak es la cantidad de veces que se repite el factor primo pk.

Teorema Fundamental de la Aritmética:

Todo número positivo mayor que 1 puede ser escrito como producto de factores primos de una sola forma. La siguiente implementación en C++ determina los factores primos de un número.

void factor(int num) 
{ 
    for(int i=2; i*i <= num; i++)      {
        while(num % i == 0)          {
           //si num es divisible por i significa que i es un factor primo
           printf("%d ",i);
           num /= i;
        }
    }
    
    if (num > 1) 
      printf("%d",num); //num es un factor primo
    
    printf("\n"); 
}

Problemas relacionados con números primos:

Aquí les dejo algunos problemas tomados del juez en línea caribeño COJ.

Conclusiones

Los números primos están presentes en varios teoremas de la Teoría de Números, por lo que saber cómo determinarlos es fundamental para poder resolver ejercicios de esta rama de las matemáticas. Los números primos también son utilizados para determinar la función Phi de Euler (cantidad de coprimos menores que un número n), el Pequeño Teorema de Fermat y la Conjetura de Goldbach. Por ahora es todo, cualquier duda déjala en los comentarios y hasta la próxima.