Algoritmo de los números primos
Contenido
Los números primos son números naturales (números enteros positivos que a veces incluyen el 0 en ciertas definiciones) mayores que 1, que no pueden formarse multiplicando dos números menores. Un ejemplo de número primo es el 7, ya que sólo puede formarse multiplicando los números 1 y 7. Otros ejemplos son 2, 3, 5, 11, etc.
Los números primos son muy utilizados en la teoría de números debido al teorema fundamental de la aritmética. Este teorema establece que los números naturales mayores que 1 son primos o pueden ser factorizados como un producto de números primos. Por ejemplo, el número 60 puede ser factorizado en un producto de números primos de la siguiente manera:
Un método para encontrar los factores primos de un número compuesto es la división de prueba. La división de prueba es uno de los algoritmos más básicos, aunque es muy tedioso. Consiste en probar cada número entero dividiendo el número compuesto en cuestión por el número entero, y determinar si, y cuántas veces, el número entero puede dividir el número uniformemente. Como ejemplo sencillo, a continuación se muestra la factorización en primos de 820 utilizando la división de prueba:
Calculadora de factorización de números primos números grandes
Para saber si un número es primo, comprueba si pasa una prueba de primalidad. La prueba utiliza primero algoritmos probabilísticos y si la probabilidad de ser primo es distinta de cero, los algoritmos se convierten en deterministas (verificación cuidadosa de los divisores potenciales).
Se trata principalmente de una convención matemática que evita muchos problemas en las definiciones y teoremas matemáticos (donde habría que excluir el 1 o tratarlo como un caso especial). Otra ventaja es que la descomposición del factor primo es única 6 = 2*3 y no 1*2*3 o 1*1*1*2*3.
Lista de números primos
En la teoría computacional de los números, hay una serie de algoritmos que permiten generar números primos de forma eficiente. Estos se utilizan en diversas aplicaciones, por ejemplo, en el hash, la criptografía de clave pública y la búsqueda de factores primos en números grandes.
Para números relativamente pequeños, es posible limitarse a aplicar la división de prueba a cada número impar sucesivo. Las cribas de primos son casi siempre más rápidas. El cribado de primos es la forma más rápida conocida de enumerar los primos de forma determinista. Hay algunas fórmulas conocidas que pueden calcular el siguiente primo, pero no hay ninguna forma conocida de expresar el siguiente primo en términos de los primos anteriores. Además, no se conoce ninguna manipulación y/o extensión general efectiva de alguna expresión matemática (incluso de las que incluyen los primos posteriores) que calcule de forma determinista el siguiente primo.
Un tamiz de primos o tamiz de números primos es un tipo de algoritmo rápido para encontrar primos. Hay muchos tamices de números primos. La criba simple de Eratóstenes (250 a.C.), la criba de Sundaram (1934), la criba aún más rápida pero más complicada de Atkin[1] (2003), y varias cribas de rueda[2] son las más comunes.
Calcular los factores primos de un número
Un número primo o entero primo – a menudo llamado simplemente «primo» para abreviar – es un número entero positivo p > 1 que no tiene divisores enteros positivos distintos de 1 y el propio p. Por ejemplo, los únicos divisores de 13 son 1 y 13, lo que hace que 13 sea un número primo, mientras que el número 24 tiene los divisores 1, 2, 3, 4, 6, 8, 12 y 24, lo que corresponde a la factorización 24 = 23 × 3, lo que hace que 24 no sea un número primo. Los números enteros positivos distintos de 1 que no son primos se llaman números compuestos.
