Cómo saber si un número es primo

Utiliza la división: La división por tentativa es una de las pruebas más sencillas para determinar la primalidad. A su vez, es una de las pruebas disponibles más rápidas, principalmente para las cifras pequeñas.

Este método consiste en la definición de un número primo. Debes dividir el número ‘N’ -en este caso será el que usaremos- entre los factores enteros más posibles. Al interesarnos en valores grandes de “N”, como N=101, no es muy común dividirlos entre los números enteros inferiores a «N». Por casualidad, hay varios trucos que funcionan para reducir el número de factores que deseas probar.

Utiliza el test de Miller-Rabin: Esta prueba funciona de manera muy similar al del pequeño teorema de Fermat, siendo más eficientes con los números Carmichael.

Utiliza el teorema de Fermat: El matemático francés Pierre de Fermat, en el año 1640, escribió el teorema que hoy día lleva su nombre, es muy ideal a la hora de decidir si un número es primo.

La prueba de Fermat es usada para determinar si un número es compuesto aún más que si es un primo, debido que se puede determinar con total certeza si es un número compuesto, pero solo señala si probablemente es un primo, por lo tanto, no es la opción más ideal.

Cabe destacar que el teorema de Fermat es útil sólo en el caso de que la división por tentativa no sea efectiva y cuando se disponga de una lista de números que suelen ser excepción al teorema.

La fórmula para encontrar los números primos:

La interpretación más razonable de la fórmula es una máquina de Turing que se para en todas sus entradas. Ésta fórmula se encarga de generar los números primos, absolutamente y sin excepción.

Aunque no existe una formula polinómica para la obtención de todos los números, tampoco existe fórmula polinómica que sólo disponga valores primos.