Ver el código de «Número primo»

{{Artículo bueno}}
{{otros usos |1=elemento primo |para=la generalización a [[anillo (matemáticas)|anillos]]|este=primos en los números enteros |otro=elemento irreducible}}
[[Archivo:Primencomposite0100.svg|thumb|400px|Números naturales de cero a cien. Los números primos están marcados en rojo.]]
[[Archivo:Prime num le 400.png|thumb|400px|La distribución de los números primos (trazos azules) hasta el 400]]
En [[matemáticas]], un '''número primo''' es un [[número natural]] mayor que 1 que tiene únicamente dos [[Divisibilidad|divisores]] positivos distintos: él mismo y el [[uno|1]].<ref>Niven y Zuckerman: ''Introducción a la teoría 
'', Editorial Trillas. México D. F., pág. 55</ref> Por el contrario, los [[número compuesto|números compuestos]] son los [[Número natural|números naturales]] que tienen algún divisor natural aparte de sí mismos y del 1, y, por lo tanto, pueden [[Factorización de enteros|factorizarse]]. El [[uno|número 1]], [[#El número 1 no se considera primo|por convenio]], no se considera ni primo ni compuesto.

Los 168{{esd}}números primos menores que [[mil|1000]] son: 

[[dos|2]], [[tres|3]], [[cinco|5]], [[siete|7]], [[once|11]], [[trece|13]], [[diecisiete|17]], [[diecinueve|19]], [[veintitrés|23]], [[veintinueve|29]], [[treinta y uno|31]], [[treinta y siete|37]], [[cuarenta y uno|41]], [[cuarenta y tres|43]], [[cuarenta y siete|47]], [[cincuenta y tres|53]], [[cincuenta y nueve|59]], [[sesenta y uno|61]], [[sesenta y siete|67]], [[setenta y uno|71]], [[setenta y tres|73]], [[setenta y nueve|79]], [[ochenta y tres|83]], [[ochenta y nueve|89]], [[noventa y siete|97]], [[ciento uno|101]], [[ciento tres|103]], [[ciento siete|107]], [[ciento nueve|109]], [[ciento trece|113]], [[Anexo:Números|127]], [[Anexo:Números|131]], [[Ciento treinta y siete|137]], [[Anexo:Números|139]], [[Anexo:Números|149]], [[Anexo:Números|151]], [[Anexo:Números|157]], [[Anexo:Números|163]], [[Anexo:Números|167]], [[Anexo:Números|173]], [[Anexo:Números|179]], [[Anexo:Números|181]], [[Anexo:Números|191]], [[Anexo:Números|193]], [[Anexo:Números|197]], [[Anexo:Números|199]], 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991 y 997 {{OEIS|id=A000040}}. 

El primer número primo a partir del número [[mil]] es el 1009, después de [[diez mil]] es el {{Nts|10007}}, a partir de [[cien mil]] es el {{Nts|100003}} e inmediatamente tras un [[millón]] es el {{Nts|1000003}}.

La propiedad de ser número primo se denomina '''primalidad'''.

En la teoría algebraica de números, los números primos se denominan números ''racionales primos'' para distinguirlos de los [[números gaussianos]] primos.<ref>Niven- Zuckerman. ''Introducción a la teoría de números''</ref> La primalidad no depende del sistema de numeración, pero sí del anillo donde se estudia la primalidad. Dos es primo racional; sin embargo tiene factores como entero gaussiano: 2 = (1+[[Número imaginario|i]])*(1-i).

El estudio de los números primos es una parte importante de la [[teoría de números]], rama de las matemáticas que trata las propiedades, básicamente aritméticas,<ref>Abramo Hefez: '' Curso de álgebbra vol.1, ISBN 9972-9394-1-3, pág. 87''</ref> de los números enteros.

Los números primos están presentes en algunas [[conjetura matemática|conjeturas]] centenarias tales como la [[hipótesis de Riemann]] y la [[conjetura de Goldbach]], resuelta por [[Harald Helfgott]] en su forma [[Conjetura débil de Goldbach|débil]].

La distribución de los números primos es un asunto reiterativo de investigación en la teoría de números: si se consideran números aisladamente, los primos parecieran estar distribuidos de modo probabilístico, pero la distribución «global» de los números primos se ajusta a leyes bien definidas.

== Historia ==
=== El Oriente prehelénico ===
[[Imagen:Os d'Ishango IRSNB.JPG|thumbnail|150px|Imagen del [[hueso de Ishango]] expuesto en el [[Real Instituto Belga de Ciencias Naturales]].]]

Las muescas presentes en el [[hueso de Ishango]], que data de hace más de {{esd|{{Nts|20000}} años}} (anterior por tanto a la aparición de la [[escritura]]) y que fue hallado por el arqueólogo [[Jean de Heinzelin de Braucourt]],<ref>[[Marcus du Sautoy]], ''La symphonie des nombres premiers'' P.42 (en francés)</ref> parecen aislar cuatro números primos: 11, 13, 17 y 19. Algunos arqueólogos interpretan este hecho como la prueba del conocimiento de los números primos. Con todo, existen muy pocos hallazgos que permitan discernir los conocimientos que tenía realmente el hombre de aquella época.<ref>''[https://web.archive.org/web/20070710020835/http://www.reunion.iufm.fr/recherche/irem/telecharger/Keller/Keller3.pdf Préhistoire de la géométrie: le problème des sources]'', artículo de Olivier Keller (en francés)</ref>

Numerosas tablillas de arcilla cocida atribuidas a las [[civilizaciones]] que se fueron sucediendo en [[Mesopotamia]] a lo largo del II milenio a.{{esd}}C. muestran la resolución de problemas aritméticos y atestiguan los conocimientos de la época. Los cálculos requerían conocer los [[inverso multiplicativo|inversos]] de los naturales, que también se han hallado en tablillas.<ref>{{Cita web
 |url=http://almez.pntic.mec.es/~agos0000/Nacimiento.html
 |título=Nacimiento de las matemáticas.
 |fechaacceso=7 de junio de 2009
 |urlarchivo=https://web.archive.org/web/20090614022738/http://almez.pntic.mec.es/~agos0000/Nacimiento.html
 |fechaarchivo=14 de junio de 2009
 }}</ref>
En el [[sistema sexagesimal]] que empleaban los [[Historia de Babilonia|babilonios]] para escribir los números, los inversos de los divisores de potencias de 60 (''números regulares'') se calculan fácilmente; por ejemplo, dividir entre 24 equivale a multiplicar por 150 (2·60+30) y correr la coma sexagesimal dos lugares. El conocimiento matemático de los babilonios necesitaba una sólida comprensión de la multiplicación, la división y la [[factorización]] de los naturales.

En las [[Matemáticas en el Antiguo Egipto|matemáticas egipcias]], el cálculo de [[fracción|fracciones]] requería conocimientos sobre las operaciones, la división de naturales y la factorización. Los egipcios solo operaban con las llamadas [[fracción egipcia|fracciones egipcias]], suma de [[fracción unitaria|fracciones unitarias]], es decir, aquellas cuyo numerador es 1, como <math>\tfrac{1}{2}, \tfrac{1}{3}, \tfrac{1}{4}, \tfrac{1}{5}, \dots</math>, por lo que las fracciones de numerador distinto de 1 se escribían como suma de inversos de naturales, a ser posible sin repetición <math>\left(  \tfrac{2}{3} = \tfrac{1}{2}+\tfrac{1}{6} \right .</math> en lugar de <math>\left . \tfrac{1}{3}+\tfrac{1}{3} \right)</math>.<ref>{{Cita libro
 |autor=Arnaldez, Roger y otros
 |título=Las antiguas ciencias del Oriente.
 |año=1988
 |editorial=Barcelona: Ediciones Orbis S.A.
| ISBN = 84-402-0159-1
}}</ref> Es por ello que, en cierta manera, tenían que conocer o intuir los números primos.<ref>{{Cita web
 |url=http://planetmath.org/encyclopedia/HistoryOfPrimeNumbers.html
 |título=History of prime numbers.
 |fechaacceso=7 de junio de 2009
 |autor=Planetmath.org
 |fechaarchivo=12 de diciembre de 2009
 |urlarchivo=https://web.archive.org/web/20091212052202/http://planetmath.org/encyclopedia/HistoryOfPrimeNumbers.html
 |deadurl=yes
 }}</ref>

=== Antigua Grecia ===
[[Archivo:Oxyrhynchus papyrus with Euclid's Elements.jpg|230px|thumb|right|Un fragmento de los ''Elementos'' de Euclides encontrado en [[Oxirrinco]]]]
La primera prueba indiscutible del conocimiento de los números primos se remonta a alrededor del año {{esd|300 a. C.}} y se encuentra en los ''[[Elementos de Euclides|Elementos]]'' de [[Euclides]] (tomos VII a IX). Euclides define los números primos, demuestra que hay infinitos de ellos, define el [[máximo común divisor]] y el [[mínimo común múltiplo]] y proporciona un método para determinarlos que hoy en día se conoce como el [[algoritmo de Euclides]]. Los ''Elementos'' contienen asimismo el [[teorema fundamental de la aritmética]] y la manera de construir un [[número perfecto]] a partir de un número primo de Mersenne.

La [[criba de Eratóstenes]], atribuida a [[Eratóstenes de Cirene]], es un método sencillo que permite encontrar números primos. Hoy en día, empero, los mayores números primos que se encuentran con la ayuda de ordenadores emplean otros algoritmos más rápidos y complejos.

=== Desde la época del Renacimiento ===
[[Archivo:Pierre de Fermat.jpg|230px|thumb|[[Pierre de Fermat]]]]
Después de las matemáticas griegas hubo pocos avances en el estudio de los números primos hasta el siglo {{versalita|xvii}}. En 1640 [[Pierre de Fermat]] estableció (aunque sin demostración) el [[pequeño teorema de Fermat]], posteriormente demostrado por [[Gottfried Wilhelm Leibniz|Leibniz]] y [[Leonhard Euler|Euler]]. Es posible que mucho antes se conociera un caso especial de dicho teorema en China.

Fermat conjeturó que todos los números de la forma 2<sup>2<sup>''n''</sup></sup>+1 eran primos (debido a lo cual se los conoce como [[número primo de Fermat|números de Fermat]]) y verificó esta propiedad hasta ''n'' = 4 (es decir, 2<sup>16</sup>&nbsp;+&nbsp;1). Sin embargo, el número de Fermat 2<sup>32</sup>&nbsp;+&nbsp;1 es compuesto (uno de sus factores primos es 641), como demostró Euler. De hecho, hasta nuestros días no se conoce ningún número de Fermat que sea primo aparte de los que ya conocía el propio Fermat.

El monje francés [[Marin Mersenne]] investigó los números primos de la forma 2<sup>''p''</sup>&nbsp;−&nbsp;1, con ''p'' primo. En su honor, se los conoce como [[número de Mersenne|números de Mersenne]].

En el trabajo de Euler en teoría de números se encuentran muchos resultados que conciernen a los números primos. Demostró la [[divergencia de la suma de los inversos de los números primos|divergencia]] de la [[suma infinita|serie]] <math>\tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{5}+\tfrac{1}{7}+\dots</math>, y en 1747 demostró que todos los [[número perfecto|números perfectos]] pares son de la forma 2<sup>''p''-1</sup>(2<sup>''p''</sup> - 1), donde el segundo factor es un número primo de Mersenne. Se cree que no existen números perfectos impares, pero todavía es una cuestión abierta.

A comienzos del siglo {{versalita|xix}}, Legendre y Gauss conjeturaron de forma independiente que, cuando ''n'' tiende a infinito, el número de primos menores o iguales que ''n'' es asintótico a <math>\tfrac{n}{\ln (n)}</math>, donde ln(''n'') es el [[logaritmo natural]] de ''n''. Las ideas que [[Bernhard Riemann]] plasmó en un trabajo de 1859 sobre la [[función zeta de Riemann|función zeta]] describieron el camino que conduciría a la demostración del [[teorema de los números primos]]. [[Jacques Hadamard|Hadamard]] y [[Charles-Jean de la Vallée Poussin|De la Vallée-Poussin]], cada uno por separado, dieron forma a este esquema y consiguieron demostrar el teorema en 1896.

Actualmente no se comprueba la primalidad de un número por [[división por tentativa|divisiones sucesivas]], al menos no si el número es relativamente grande.

Durante el siglo {{versalita|xix}} se desarrollaron algoritmos para saber si un número es primo o no factorizando completamente el número siguiente (p+1) o el anterior (p-1). Dentro del primer caso se encuentra el [[test de Lucas-Lehmer]], desarrollado a partir de 1856. Dentro del segundo caso se encuentra el [[test de Pépin]] para los números de Fermat (1877). El caso general de test de primalidad cuando el número inmediatamente anterior se encuentra completamente factorizado se denomina [[test de Lucas]].

Posteriormente se encontraron algoritmos de primalidad con solo obtener una factorización parcial de p+1 o p-1. Ejemplos de estos algoritmos son el [[Teorema de Proth|test de Proth]] (desarrollado alrededor de 1878) y el [[test de Pocklington]] (1914). En estos algoritmos se requiere que el producto de los factores primos conocidos de p-1 sea mayor que la raíz cuadrada de ''p''. Más recientemente, en 1975, Brillhart, Lehmer y Selfridge desarrollaron el [[test de primalidad BLS]] que solo requiere que dicho producto sea mayor que la raíz cúbica de ''p''. El mejor método conocido de esta clase es el [[Serguéi Koniaguin|test de Koniaguin y Pomerance]] del año 1997, que requiere que dicho producto sea mayor que ''p''<sup>3/10</sup>.<ref>{{Cita libro| apellidos = Crandall |nombre=Richard |título=Prime numbers, a computational perspective | url = https://archive.org/details/primenumberscomp0000cran |año=2001 |editorial=Nueva York: Springer-Verlag |isbn = 0-387-94777-9}}</ref><ref>{{Cita web |apellido=Bernstein |nombre=Daniel |título=Prime tests |url=http://cr.yp.to/primetests.html |fechaacceso=1 de julio de 2009}}</ref>

A partir de la década de 1970 varios investigadores descubrieron algoritmos para determinar si cualquier número es primo o no con complejidad subexponencial, lo que permite realizar tests en números de miles de dígitos, aunque son mucho más lentos que los métodos anteriores. Ejemplos de estos algoritmos son el [[test de Adleman-Pomerance-Rumely|test APRT-CL]] (desarrollado en 1979 por Adleman, Pomerance y Rumely, con mejoras introducidas por Cohen y Lenstra en 1984), donde se usan los factores de p<sup>m</sup>-1, donde el exponente m depende del tamaño del número cuya primalidad se desea verificar, el [[test de primalidad por curvas elípticas]] (desarrollado en 1986 por S. Goldwasser, J. Kilian y mejorado por A. O. L. Atkin), que entrega un certificado consistente en una serie de números que permite después confirmar rápidamente si el número es primo o no. El desarrollo más reciente es el [[test de primalidad AKS]] (2002), que si bien su complejidad es polinómica, para los números que puede manejar la tecnología actual es el más lento de los tres.

Durante mucho tiempo, se pensaba que la aplicación de los números primos era muy limitada fuera de la [[matemática pura]].<ref>{{Cita libro
| apellidos = Singh
 |nombre=Simon
 |enlaceautor=Simon Singh
 |título=El enigma de Fermat
 |año=1998
 |editorial=Editorial Planeta S.A
 |id=ISBN 978-84-08-02375-3.
 |capítulo=Pág. 126
}}</ref><ref>{{Cita web
 |url=http://pinux.info/primos/curiosidades.html
 |título=Curiosidades sobre números primos.
 |fechaacceso=5 de junio de 2009

 |autor=Carles Pina i Estany
 |año=2005
}}
</ref> Esto cambió en los años 1970 con el desarrollo de la [[criptografía de clave pública]], en la que los números primos formaban la base de los primeros algoritmos, tales como el algoritmo [[RSA]].

Desde 1951, el mayor número primo conocido siempre ha sido descubierto con la ayuda de [[Computadora electrónica|ordenadores]]. La búsqueda de números primos cada vez mayores ha suscitado interés incluso fuera de la comunidad matemática. En los últimos años han ganado popularidad proyectos de [[computación distribuida]] tales como el [[GIMPS]], mientras los matemáticos siguen investigando las propiedades de los números primos.

== El número 1 no se considera primo ==

La cuestión acerca de si el número 1 debe o no considerarse primo está basada en la convención. Ambas posturas tienen sus ventajas y sus inconvenientes. De hecho, hasta el siglo {{versalita|xix}}, los matemáticos en su mayoría lo consideraban primo. Muchos trabajos matemáticos siguen siendo válidos a pesar de considerar el 1 como un número primo, como, por ejemplo, el de [[Moritz Abraham Stern|Stern]] y Zeisel. La lista de [[Derrick Norman Lehmer]] de números primos hasta el 10.006.721, reimpresa hasta el año 1956<ref>Hans Riesel, ''Prime Numbers and Computer Methods for Factorization''. New York: Springer (1994): 36 (en inglés)</ref> empezaba con el 1 como primer número primo.<ref>Richard K. Guy & John Horton Conway, ''The Book of Numbers''. New York: Springer (1996): 129 - 130 (en inglés)</ref>

Actualmente, la comunidad matemática se inclina por no considerar al 1 en la lista de los números primos. Esta convención, por ejemplo, permite una formulación muy económica del [[teorema fundamental de la aritmética]]: «''todo número natural tiene una representación '''única''' como producto de factores primos, salvo el orden''».<ref>{{Cita libro|apellidos=Gowers |nombre=T |enlaceautor=William Timothy Gowers |año=2002 |página=[https://archive.org/details/mathematicsverys00gowe_114/page/n125 118]|cita=La exclusión aparentemente arbitraria del 1 de la definición de número primo … no expresa ningún conocimiento profundo sobre los números: se trata simplemente de un convenio útil, adoptado para que solo haya una manera de factorizar cualquier número en sus factores primos |título=Mathematics: A Very Short Introduction |url=https://archive.org/details/mathematicsverys00gowe_114 |editorial=[[Oxford University Press]] |isbn=0-19-285361-9}}</ref><ref>"[http://primes.utm.edu/notes/faq/one.html Why is the number one not prime?]" (en inglés), accedido el 31-05-2009.</ref> Además, los números primos tienen numerosas propiedades de las que carece el 1, tales como la relación del número con el valor correspondiente de la [[función φ de Euler]] o la [[función divisor]].<ref>"[https://web.archive.org/web/20070825005316/http://www.geocities.com/primefan/Prime1ProCon.html Arguments for and against the primality of 1]" (en inglés), accedido el 31-05-2009.</ref> Cabe también la igualdad para todo <math> n </math> entero positivo, <math>1= 1^n </math>, lo que permitiría decir que tiene <math> n </math> factores.<ref>Se puede probar por el principio de inducción matemática</ref>

== Propiedades de los números primos ==
=== Teorema fundamental de la aritmética ===
{{AP|Teorema fundamental de la aritmética}}

[[Archivo:Prime rectangles.png|thumb|Esta ilustración muestra que el 11 es un número primo, pero el 12 no lo es.]]

El [[teorema fundamental de la aritmética]] establece que todo número natural tiene una representación única como producto de factores primos, salvo el orden. Un mismo factor primo puede aparecer varias veces. El 1 se representa entonces como un [[producto vacío]].

Se puede considerar que los números primos son los «ladrillos» con los que se construye cualquier número natural. Por ejemplo, se puede escribir el número 23.244 como producto de 2<sup>2</sup>·3·13·149, y cualquier otra factorización del 23.244 como producto de números primos será idéntica excepto por el orden de los factores.

La importancia de este teorema es una de las razones para excluir el 1 del conjunto de los números primos. Si se admitiera el 1 como número primo, el enunciado del teorema requeriría aclaraciones adicionales.

A partir de esta unicidad en la factorización en factores primos se desarrollan otros conceptos muy utilizados en matemáticas, tales como el [[mínimo común múltiplo]], el [[máximo común divisor]] y la [[coprimalidad]] de dos o más números. Así,
* El [[mínimo común múltiplo]] de dos o más números es el menor de los múltiplos comunes de todos ellos. Para calcularlo, se descomponen los números en factores primos y se toman los factores comunes y no comunes con su máximo exponente. Por ejemplo, el mínimo común múltiplo de 10=2·5 y 12=2<sup>2</sup>·3 es 60=2<sup>2</sup>·3·5.
* El [[máximo común divisor]] de dos o más números es el mayor de los divisores comunes de todos ellos. Es igual al producto de los factores comunes con su mínimo exponente. En el ejemplo anterior, el máximo común divisor de 10 y 12 es 2.
* Finalmente, dos o más números son [[primos entre sí|coprimos]], o primos entre sí, si no tienen ningún factor primo común; es decir, si su máximo común divisor es 1. Un número primo es, así, coprimo con cualquier número natural que no sea múltiplo de él mismo.

=== Otras propiedades ===
* En su escritura en el [[sistema de numeración decimal]], todos los números primos, salvo el 2 y el 5, tiene como el guarismo de las unidades uno de estos: 1, 3, 7 o 9. En general, en cualquier sistema de numeración, todos los números primos salvo un número finito acaban en una cifra que es [[números primos entre sí|coprima]] con la base.
* De lo anterior se deduce que todos los números primos salvo el 2 son de la forma [[número primo pitagórico|4''n'' + 1]] o bien 4''n'' + 3. Igualmente, todos los números primos salvo el 2 y el 3 son de la forma 6''n'' + 1 o 6''n'' - 1.
* En la progresión aritmética 3, 7, 11, 15, 19, 23, 27, 31, …, hay una cantidad infinita de números primos de la forma 4n-1, n natural.<ref>G.N. Berman: ''Un paseo por la teoría de los números'', Editorial URSS, Moscú 2007, pág. 207 </ref>
* En la progresión aritmética 7, 13, 19, 25, 31, 37, 43, 49, 55, 61, 67, …, hay una cantidad infinita de números primos de la forma 6k+1, k natural.<ref> Berman: Op. cit </ref>
* [[Lema de Euclides]]: Si ''p'' es un número primo y [[Divisibilidad|divisor]] del producto de [[número entero|números enteros]] ''ab'', entonces ''p'' es divisor de ''a'' o de ''b''.
* [[Pequeño teorema de Fermat]]: Si ''p'' es primo y ''a'' es algún número natural diferente de 1, entonces ''a''<sup>''p''</sup> - ''a'' es divisible por ''p''.
* Si un número p no divide al número m, entonces (p; m) =1<ref> T. M. Aosto: Introducción a la teoría analítica de números, Editorial Reverté S.A. Barcelona, 1980 </ref>
* Si ''p'' es primo distinto de 2 y 5, <math>\tfrac{1}{p}</math> siempre es un [[número periódico]] en su representación decimal, de periodo ''p''&nbsp;−&nbsp;1 o un divisor de ''p''&nbsp;−&nbsp;1. Esto se puede deducir directamente a partir del pequeño teorema de Fermat. <math>\tfrac{1}{p}</math> expresado en base ''q'' (en lugar de en base 10) tiene propiedades similares, siempre que ''p'' no sea un factor primo de ''q''.
* [[Teorema de Wilson]]: Un número natural ''n'' > 1 es primo [[si y solo si]] el [[factorial]] (''n'' - 1)! + 1 es divisible por ''n''. Asimismo, un número natural ''n'' > 4 es compuesto si y solo si (''n'' - 1)! es divisible por ''n''.
* La [[característica (álgebra)|característica]] de todo cuerpo es, o bien cero, o bien un número primo.
* [[Teorema de Sylow|Primer teorema de Sylow]]: Si ''G'' es un [[grupo (matemática)|grupo]] finito, ''p'' primo y ''p''<sup>''n''</sup> es la mayor potencia de ''p'' que divide el [[orden p-ádico|orden]] de ''G''. Entonces, existe un subgrupo de ''G'' de orden ''p''<sup>n</sup>.
* [[Teorema de Cauchy (teoría de grupos)|Teorema de Cauchy]]: Si ''G'' es un grupo finito y ''p'' es un número primo que divide al orden de ''G'', entonces ''G'' contiene un elemento de orden ''p''.
* La [[constante de Copeland-Erdős]] 0,235711131719232931374143…, obtenida por [[concatenación]] de los números primos en el sistema decimal, es un [[número irracional]].
* El valor de la [[función zeta de Riemann]] en cada punto del [[plano complejo]] se da como una continuación meromorfa de una función definida por un producto sobre el conjunto de todos los primos para Re(''s'') > 1:
::<math>\zeta(s)=
\sum_{n=1}^\infin \frac{1}{n^s} = \prod_{p} \frac{1}{1-p^{-s}}.</math>
:En la región donde es convergente, este producto indexado por los números primos se puede calcular, obteniéndose diversos valores, algunos de ellos importantes en teoría de números. Los dos primeros son:
::<math>\prod_{p} \frac{1}{1-p^{-1}} = \infty </math> (correspondiente a la [[Serie armónica (matemática)|serie armónica]], relacionado con la [[Serie de los inversos de los números primos#Primera prueba (Prueba original de Euler)|infinitud de números primos]]).
::<math>\prod_{p} \frac{1}{1-p^{-2}}= \frac{\pi^2}{6}</math> (correspondiente al [[problema de Basilea]]).
::En general <math>\frac{1}{\pi^n}\prod_{p} \frac{1}{1-p^{-n}}</math> es un número racional cuando ''n'' es un número entero positivo par.
* El [[anillo (matemática)|anillo]] <math>\mathbb{Z}/p\mathbb{Z}</math> es un [[cuerpo (matemática)|cuerpo]] si y solo si ''p'' es primo. Equivalentemente: ''p'' es primo si y solo si [[función φ de Euler|φ(''p'')]] = ''p'' − 1.
* Si ''p'' > 1, el [[polinomio]] ''x''<sup>&nbsp;''p''-1</sup>+''x''<sup>&nbsp;''p''-2</sup>+ ··· + 1 es [[polinomio irreducible|irreducible]] sobre <math>\mathbb{Z}/p\mathbb{Z}</math> si y solo si ''p'' es primo.
* Un número natural ''n'' es primo si y solo si el ''n''-ésimo [[polinomio de Chebyshov]] de la primera especie T<sub>''n''</sub>(''x''), dividido entre ''x'', es <math> 2 = i(1-i)^2</math> irreducible en <math>\mathbb{Z}[x]</math>. Además, T<sub>''n''</sub>(''x'') ≡ x<sup>''n''</sup> si y solo si ''n'' es primo.
* No todo número primo es un número gaussiano primo; tal el caso de 2, que como entero gaussiano admite la descomposición <math> 2 = i(1-i)^2</math> don de la norma de <math> 1-i</math> es 2, por lo tanto no es unidad en Z[i].
* Los números primos de la forma <math> 4n+1</math> son igual a la suma de dos cuadrados perfectos; por lo que no son números gaussianos primos. En tanto que los números primos de la forma <math> 4n+3</math> sí son números gaussianos primos.
* Todo número racional primo es un número gaussiano entero, sin ser necesariamente número gaussiano primo.<ref>Niven Zuckerman. ''Introducción a la teoría de números''</ref>

=== Números primos y funciones aritméticas ===
Las [[función aritmética|funciones aritméticas]], es decir, [[función matemática|funciones]] [[número real|reales]] o [[número complejo|complejas]], definidas sobre un conjunto de números naturales, desempeñan un papel crucial en la [[teoría de números]]. Las más importantes son las [[función multiplicativa|funciones multiplicativas]], que son aquellas funciones ''f'' en las cuales, para cada par de números [[coprimos]] (''a'',''b'') se tiene
:<math>f(ab)=f(a)f(b) \,\!</math>.

Algunos ejemplos de funciones multiplicativas son la [[función φ de Euler]], que a cada ''n'' asocia el número de enteros positivos menores y coprimos con ''n'', y las funciones [[función divisor|τ]] y [[función divisor|σ]], que a cada ''n'' asocian respectivamente el número de divisores de ''n'' y la suma de todos ellos. El valor de estas funciones en las [[potencia (matemática)|potencias]] de números primos es
:<math>\operatorname{\varphi}(p^m)=p^m-p^{m-1}</math>,
:<math>\operatorname{\tau}(p^m)=m+1</math>,
:<math>\operatorname{\sigma}(p^m)=1+p^2+p^3+\cdots+p^m</math>.

Gracias a la propiedad que las define, las funciones aritméticas pueden calcularse fácilmente a partir del valor que toman en las potencias de números primos. De hecho, dado un número natural ''n'' de factorización
:<math>n=p_1^{q_1}\cdots p_a^{q_a}</math>

se tiene que
:<math>f(n)=f(p_1^{q_1})\cdots f(p_a^{q_a})</math>

con lo que se ha reconducido el problema de calcular ''f''(''n'') al de calcular ''f'' sobre las potencias de los números primos que dividen ''n'', valores que son generalmente más fáciles de obtener mediante una fórmula general. Por ejemplo, para conocer el valor de la función φ sobre ''n''=450=2·3<sup>2</sup>·5<sup>2</sup> basta con calcular
:<math>\operatorname{\varphi}(450)=\operatorname{\varphi}(2)\cdot\operatorname{\varphi}(3^2)\cdot\operatorname{\varphi}(5^2)=(2-1)\cdot(9-3)\cdot(25-5)=120</math>.

== Características del conjunto de los números primos ==
=== Infinitud de los números primos ===
{{VT|Infinitud de los números primos}}

Existen infinitos números primos. Euclides realizó la primera [[segundo teorema de Euclides|demostración]] alrededor del año {{esd|300 a. C.}} en el libro IX de su obra ''[[Elementos]]''.<ref> {{Cita libro
| apellidos = &nbsp;
 |nombre=Euclides
 |enlaceautor=Euclides
 |título=Elementos
 |año=1991-1996
 |editorial=Obra completa, Madrid, [[Editorial Gredos]]
 |isbn = 978-84-249-1463-9|capítulo=Vol. II, libro IX, proposición 20.
}}
</ref> Una adaptación común de esta demostración original sigue así: Se toma un conjunto arbitrario pero finito de números primos ''p''<sub>1</sub>, ''p''<sub>2</sub>, ''p''<sub>3</sub>, ···, ''p''<sub>''n''</sub>, y se considera el producto de todos ellos más uno, <math> q=p_1\times p_2\times p_3 \ldots \times p_n + 1</math>. Este número es obviamente mayor que 1 y distinto de todos los primos ''p''<sub>''i''</sub> de la lista. El número ''q'' puede ser primo o compuesto. Si es primo tendremos un número primo que no está en el conjunto original. Si, por el contrario, es compuesto, entonces existirá algún factor ''p'' que divida a ''q''. Suponiendo que ''p'' es alguno de los ''p''<sub>''i''</sub>, se deduce entonces que ''p'' divide a la diferencia <math>q - p_1 \times p_2 \times p_3 \ldots \times p_n = 1</math>, pero ningún número primo divide a 1, es decir, se ha llegado a un absurdo por suponer que ''p'' está en el conjunto original. La consecuencia es que el conjunto que se escogió no es exhaustivo, ya que existen números primos que no pertenecen a él, y esto es independiente del conjunto finito que se tome.

Por tanto, el conjunto de los números primos es infinito.

Si se toma como conjunto el de los ''n'' primeros números primos, entonces <math> q=p_1\times p_2\times p_3 \ldots \times p_n+1 = p_n\sharp +1</math>, donde ''p''<sub>''n''</sub># es lo que se llama [[primorial]] de ''p''<sub>''n''</sub>. Un número primo de la forma ''p''<sub>''n''</sub># +1 se denomina [[número primo de Euclides]] en honor al matemático griego. También se puede elaborar una demostración similar a la de Euclides tomando el producto de un número dado de números primos ''menos'' uno, el lugar del producto de esos números primos ''más'' uno. En ese sentido, se denomina [[número primo primorial]] a un número primo de la forma ''p''<sub>''n''</sub># ± 1.

No todos los números de la forma ''p''<sub>''n''</sub># +1 son primos. En este caso, como se sigue de la demostración anterior, todos los factores primos deberán ser mayores que ''n''. Por ejemplo: 2·3·5·7·11·13+1=30031=59·509

Otros matemáticos han demostrado la [[infinitud de los números primos]] con diversos métodos procedentes de áreas de las matemáticas tales como al [[álgebra conmutativa]] y la [[topología]].<ref>{{Cita web
 |url=http://gaussianos.com/demostracion-topologica-de-la-infinitud-de-los-numeros-primos/
 |título=Demostración topológica de la infinitud de los números primos.
 |fechaacceso=5 de junio de 2009

 |autor=DiAmOnD
 |año=2008
}}</ref>
Algunas de estas demostraciones se basan en el uso de [[sucesión matemática|sucesiones]] infinitas con la propiedad de que cada uno de sus términos es coprimo con todos los demás, por lo que se crea una [[biyección]] entre los términos de la sucesión y un subconjunto (infinito) del conjunto de los primos.

Una sucesión que cumple dicha propiedad es la [[sucesión de Euclides-Mullin]], que deriva de la demostración euclídea de la infinitud de los números primos, ya que cada uno de sus términos se define como el factor primo más pequeño de uno más el producto de todos los términos anteriores. La [[sucesión de Sylvester]] se define de forma similar, puesto que cada uno de sus términos es igual a uno más el producto de todos los anteriores. Aunque los términos de esta última sucesión no son necesariamente todos primos, cada uno de ellos es coprimo con todos los demás, por lo que se puede escoger cualquiera de sus factores primos, por ejemplo, el menor de ellos, y el conjunto resultante será un conjunto infinito cuyos términos son todos primos.

==== Otros enunciados que implican la infinitud de los números primos ====
Un resultado aún más fuerte, y que implica directamente la infinitud de los números primos, fue descubierto por Euler en el siglo {{versalita|xviii}}. Establece que la [[suma de los inversos de los números primos|serie]] <math>\tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{5}+\tfrac{1}{7}+\dots</math> es [[Serie divergente|divergente]]. Uno de los [[teoremas de Mertens]] concreta más, estableciendo que
:<math>\sum_{p\leq n} \frac{1}{p}=\ln \ln n+O(1)</math><ref>Véase, por ejemplo, ''An Introduction to the Theory of Numbers'', p. 24. (en inglés)</ref>
donde la expresión ''O''(1) indica que ese término está acotado entre -''C'' y ''C'' para ''n'' mayor que ''n''<sub>0</sub>, donde los valores de ''C'' y ''n''<sub>0</sub> no están especificados.<ref>En general, en la notación de Landau, <math>\scriptstyle f(n) \in O(g(n))</math> indica que <math>\scriptstyle f(n)</math> está ''dominada asintóticamente'' por <math>\scriptstyle O(g(n))</math>, es decir, <math>\scriptstyle \limsup_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| < \infty</math>. Para más información, lea ''[[notación de Landau]]''.</ref>

Otro resultado es el [[Teorema de Dirichlet sobre progresiones aritméticas|teorema de Dirichlet]], que dice así:
{{teorema|1=En toda [[progresión aritmética]] ''a''<sub>''n''</sub> = ''a'' + ''n''·''q'', donde los enteros positivos ''a'', ''q'' ≥ 1 son [[primos entre sí]], existen infinitos términos que son primos.}}

El [[postulado de Bertrand]] enuncia así:
{{teorema|Si ''n'' es un número natural mayor que 3, entonces siempre existe un número primo ''p'' tal que ''n'' < ''p'' < 2''n''- 2.}}
Una manera más débil pero elegante de formularlo es que, si ''n'' es un número natural mayor que 1, entonces siempre existe un número primo ''p'' tal que ''n'' < ''p'' < 2''n''. Esto supone que, en una [[progresión geométrica]] de primer término entero mayor que 3 y razón igual a 2, entre cada término de la progresión y el siguiente, se tiene al menos un número primo.

=== Frecuencia de los números primos ===
{{VT|Teorema de los números primos}}

:{| class="wikitable" align="right" style="text-align: right"
! <math>n</math>
! <math>\pi (n)</math>
! <math>\pi (n) - \tfrac{n}{\ln n}</math>
! <math>\mathrm{Li} (n) - \pi (n)</math>
! <math>\tfrac{n}{\pi(n)}</math>
|-
| 10
| 4
| −0,3
| 2,2
| 2,500
|-
| 10<sup>2</sup>
| 25
| 3,3
| 5,1
| 4,000
|-
| 10<sup>3</sup>
| 168
| 23
| 10
| 5,952
|-
| 10<sup>4</sup>
| 1.229
| 143
| 17
| 8,137
|-
| 10<sup>5</sup>
| 9.592
| 906
| 38
| 10,425
|-
| 10<sup>6</sup>
| 78.498
| 6.116
| 130
| 12,740
|-
| 10<sup>7</sup>
| 664.579
| 44.158
| 339
| 15,047
|-
| 10<sup>8</sup>
| 5.761.455
| 332.774
| 754
| 17,357
|-
| 10<sup>9</sup>
| 50.847.534
| 2.592.592
| 1.701
| 19,667
|-
| 10<sup>10</sup>
| 455.052.511
| 20.758.029
| 3.104
| 21,975
|-
| 10<sup>11</sup>
| 4.118.054.813
| 169.923.159
| 11.586
| 24,283
|-
| …
| …
| …
| …
| …
|}

[[Archivo:PrimeNumberTheorem.png|thumb|300px|Comparación entre las funciones [[función π|π(''n'')]] (azul), ''n'' / ln ''n'' (verde) y Li(''n'') (rojo); se puede ver que la aproximación de π(''n'') con Li(''n'') es mejor que la que hay con <math>\tfrac{n}{\ln n}</math>]]

Una vez demostrado la infinitud de los números primos, cabe preguntarse cómo se distribuyen los primos entre los números naturales, es decir, cuán frecuentes son y dónde se espera encontrar el ''n''-ésimo número primo. Este estudio lo iniciaron [[Carl Friedrich Gauss|Gauss]] y [[Legendre]] de forma independiente a finales del siglo {{versalita|xviii}}, para el cual introdujeron la [[función π|función enumerativa de los números primos]] π(''n''), y conjeturaron que su valor fuese aproximadamente
:<math>\pi(n)\sim\frac{n}{\ln n}</math>.<ref>Con esta expresión se quiere decir que el [[límite (matemática)|límite]] de la razón entre las dos expresiones tiende a 1 cuando ''n'' tiende a infinito.</ref>

El empeño de demostrar esta conjetura abarcó todo el siglo {{versalita|xix}}. Los primeros resultados fueron obtenidos entre 1848 y 1859 por [[Pafnuti Chebyshov|Chebyshov]], quien demostró utilizando métodos puramente [[aritmética|aritméticos]] la existencia de dos constantes ''A'' y ''B'' tales que
:<math>A\leq \frac{\pi(n)}{\frac{n}{\ln n}} \leq B</math>
para ''n'' suficientemente grande. Consiguió demostrar que, si existía el límite del cociente de aquellas expresiones, este debía ser 1.

[[Jacques Hadamard|Hadamard]] y [[Charles Jean de la Vallée-Poussin|De la Vallée-Poussin]] elaboraron una demostración en 1896, independientemente el uno del otro, usando métodos similares, basados en el uso de la [[función zeta de Riemann]], que había sido introducida por [[Bernhard Riemann]] en 1859. Hubo que esperar hasta 1949 para encontrar una demostración que usara solo métodos elementales (es decir, sin usar el [[análisis complejo]]). Esta demostración fue ideada por [[Atle Selberg|Selberg]] y [[Paul Erdős|Erdős]]. Actualmente, se conoce el teorema como [[teorema de los números primos]].

El mismo [[Carl Friedrich Gauss|Gauss]] introdujo una estimación más precisa, utilizando la función [[logaritmo integral]]:
:<math>\pi(n)\approx \mathrm{Li}(n)=\int_2^n \frac{1}{\ln x}\mathrm{d}x</math>.

En 1899 De la Vallée-Poussin demostró que el error que se comete aproximando <math>\pi(n)</math> de esta forma es
:<math> \pi(n)-\mathrm{Li}(n) = O \left(n \mathrm{e}^{-a\sqrt{\ln n}}\right)=O\left(\frac{n}{(\ln n)^m}\right)</math>
para una constante positiva ''a'' y para cada entero ''m''. Este resultado fue ligeramente mejorado a lo largo de los años. Por otra parte, en 1901 [[Helge von Koch|Von Koch]] mostró que si la [[hipótesis de Riemann]] era cierta, se tenía la siguiente estimación, más precisa:<ref>{{Cita web
 |url=http://www.springerlink.com/content/077g4j008x57p021/
 |título=Sur la distribution des nombres premiers
 |fechaacceso=6 de junio de 2009
 |autor=von Koch, Helge
 |enlaceautor=Helge von Koch
 |año=1901
 |editorial=SpringerLink
 }}</ref>

:<math> \left | \pi(n) - \mathrm{Li}(n) \right | = O\left(\sqrt n \ln n\right). </math>

Una forma equivalente al teorema de los números primos es que p<sub>''n''</sub>, el ''n''-ésimo número primo, queda bien aproximado por ''n''ln(''n''). En efecto, ''p''<sub>''n''</sub> es estrictamente mayor que este valor.

=== Diferencia entre dos primos consecutivos ===
{{AP|Diferencia entre dos números primos consecutivos}}
Ligado a la distribución de los números primos se encuentra el estudio de los [[distancia entre dos números primos consecutivos|intervalos entre dos primos consecutivos]]. Este intervalo, con la única salvedad del que hay entre el 2 y el 3, debe ser siempre igual o mayor que 2, ya que entre dos números primos consecutivos al menos hay un número par y por tanto compuesto. Si dos números primos tienen por diferencia 2, se dice que son [[números primos gemelos|''gemelos'']], y con la salvedad del «triplete» formado por los números 3, 5 y 7, los números gemelos se presentan siempre de dos en dos. Esto también es fácil de demostrar: entre tres números impares consecutivos mayores que 3 siempre hay uno que es múltiplo de 3, y por tanto compuesto. Los primeros pares de números primos gemelos son (3,5), (5,7), (11, 13), (17, 19) y (29, 31).

Por otra parte, la diferencia entre primos consecutivos puede ser tan grande como se quiera. La demostración es relativamente sencilla: 

Sea un número natural <math>n</math>. Entonces, todos los números de la forma 

<math display="inline">(n+1)!+i</math>

son números compuestos si <math>2\leq i \leq n+1</math>, pues <math>1<i<(n+1)+i</math> y <math>\frac{(n+1)!+i}{i}= (i-1)!\cdot(i+1)(i+2)...(n)(n+1)+1 \in \mathbb{N}  </math>.

Se puede construir así una lista con <math>n</math> números compuestos, y dado que <math>n</math> es un número natural arbitrario, entonces el intervalo puede hacerse tan grande como se desee. 

Por ejemplo, si se requiere construir un intervalo de cinco números consecutivos donde ninguno sea un número primo, se hace <math>n=5</math>. Estos valores corresponden a:

:<math>6!+2=722=2 \cdot 361</math>
:<math>6!+3=723=3 \cdot 241</math>
:<math>6!+4=724=4 \cdot 181</math>
:<math>6!+5=725=5 \cdot 145</math>
:<math>6!+6=726=6 \cdot 121</math>

El siguiente valor, 6!+7=727, es primo.<ref>Nótese que esto no tiene por qué ser verdad en general, por ejemplo, si ''n'' es impar, se tiene que ''n''!+(''n''+1) es divisible entre 2.</ref> De todas formas, el menor número primo que dista del siguiente en ''n'' es generalmente mucho menor que el factorial, por ejemplo, el caso más pequeño de dos primos consecutivos separados de ocho unidades es (89, 97), mientras que 8! es igual a 40.320.

La sucesión de las diferencias entre primos consecutivos<ref>{{OEIS|A001223}}</ref> ha sido profusamente estudiada en matemáticas, y alrededor de este concepto se han establecido muchas [[#Conjeturas|conjeturas]] que permanecen sin resolver.

=== Conclusión ===
[[Archivo:PrimeNumbersSmall.png|thumb|La distribución de todos los números primos comprendidos entre 1 y {{Nts|76800}}, de izquierda a derecha y de arriba abajo. Cada pixel representa un número. Los píxeles negros representan números primos; los blancos representan números no primos.]]
[[Archivo:Primenumbers2310inv.png|thumb|Imagen con 2310 columnas que conserva múltiplos de 2, 3, 5, 7 y 11 en las columnas respectivas. Como cabe esperar, los números primos caerán en columnas concretas si los números están ordenados de izquierda a derecha y el ancho es un múltiplo de un número primo. Sin embargo, los números primos también quedan distribuidos de manera ordenada en construcciones espirales como la [[espiral de Ulam]], ya que tienden a concentrarse en algunas diagonales concretas y no en otras.]]

El modelado de la distribución de los números primos es un tema de investigación recurrente entre los teóricos de números. La primalidad de un número concreto es (hasta ahora) impredecible a pesar de que existen leyes, como el [[teorema de los números primos]] y el [[postulado de Bertrand]], que gobiernan su distribución a gran escala. [[Leonhard Euler]] comentó:

{{cita|1=Hasta el día de hoy, los matemáticos han intentado en vano encontrar algún orden en la sucesión de los números primos, y tenemos motivos para creer que es un misterio en el que la mente jamás penetrará.<ref>Julian Havil, ''Gamma: Exploring Euler's Constant'' (tapa dura). Princeton: [[Princeton University Press]] (2003): 163 (en inglés)</ref>
}}
En una conferencia de 1975, el matemático germano-estadounidense [[Don Zagier]] comentó:

{{cita|1=Hay dos hechos sobre la distribución de los números primos de los que espero convencerles de forma tan incontestable que quedarán permanentemente grabados en sus corazones. El primero es que, a pesar de su definición simple y del papel que desempeñan como ladrillos con los que se construyen los números naturales, los números primos crecen como malas hierbas entre los números naturales, y no parecen obedecer ninguna otra ley que la del azar, y nadie puede predecir dónde brotará el siguiente. El segundo hecho es aún más asombroso, ya que dice justo lo contrario: que los números primos muestran una regularidad pasmosa, que hay leyes que gobiernan su comportamiento, y que obedecen estas leyes con precisión casi militar.<ref>Julian Havil, ''Gamma: Exploring Euler's Constant'' (tapa dura). Princeton: Princeton University Press (2003): 171</ref>
}}

== Encontrar números primos ==
=== Tests de primalidad ===
{{AP|Test de primalidad}}
[[Archivo:Sieve_of_Eratosthenes_animation.gif|thumb|300px|La '''[[criba de Eratóstenes]]''' fue concebida por [[Eratóstenes de Cirene]], un [[matemático]] [[Antigua Grecia|griego]] del {{esd|siglo {{versalita|iii}} a. C.}} Es un [[algoritmo]] sencillo que permite encontrar todos los números primos menores o iguales que un número dado.]]
La [[criba de Eratóstenes]] es una manera sencilla de hallar todos los números primos menores o iguales que un número dado. Se basa en confeccionar una lista de todos los números naturales desde el 2 hasta ese número y tachar repetidamente los múltiplos de los números primos ya descubiertos. La [[criba de Atkin]], más moderna, tiene una mayor complejidad, pero si se optimiza apropiadamente también es más rápida. También existe una reciente [[criba de Sundaram]] que genera únicamente números compuestos, siendo los primos los números faltantes.

En la práctica, lo que se desea es determinar si un número dado es primo sin tener que confeccionar una lista de números primos. Un método para determinar la primalidad de un número es la [[división por tentativa]], que consiste en dividir sucesivamente ese número entre los números primos menores o iguales a su raíz cuadrada. Si alguna de las divisiones es exacta, entonces el número no es primo; en caso contrario, es primo. Por ejemplo, dado ''n'' menor o igual que 120, para determinar su primalidad basta comprobar si es divisible entre 2, 3, 5 y 7, ya que el siguiente número primo, 11, ya es mayor que √120. Es el test de primalidad más sencillo, y rápidamente pierde su utilidad a la hora de comprobar la primalidad de números grandes, ya que el número de factores posibles crece demasiado rápido a medida que crece el número potencialmente primo.

En efecto, el número de números primos menores que ''n'' es aproximadamente
:<math>\frac {n}{\ln n - 1}</math>.
De esta forma, para determinar la primalidad de ''n'', el mayor factor primo que se necesita no es mayor que {{raíz|''n''}}, dejando el número de candidatos a factor primo en cerca de
:<math>\frac {\sqrt{n}}{\ln\sqrt{n} - 1}</math>.
Esta expresión crece cada vez más lentamente en función de ''n'', pero, como los ''n'' grandes son de interés, el número de candidatos también se hace grande: por ejemplo, para {{nowrap|''n'' {{=}} 10<sup>20</sup>}} se tienen 450 millones de candidatos.

Asimismo, existen otros muchos tests de primalidad deterministas que se basan en propiedades que caracterizan a los números primos, pero su utilidad computacional depende mucho del test usado. Por ejemplo, se podría emplear el [[teorema de Wilson]] para calcular la primalidad de un número, pero tiene el inconveniente de requerir el cálculo de un [[factorial]], una operación computacionalmente prohibitiva cuando se manejan números grandes. Aquí entra en juego el [[tiempo de ejecución]] del algoritmo empleado, que se expresa en la [[notación de Landau]]. Para poder determinar la primalidad de números cada vez más grandes (de miles de cifras) se buscan aquellos algoritmos cuyo tiempo de ejecución crezca lo más lentamente posible, a ser posible, que se pueda expresar como un [[tiempo polinómico|polinomio]]. Si bien el [[test de primalidad AKS]] cumple con esta condición, para el rango de números que se usa en la práctica este algoritmo es extremadamente lento.

Por otra parte, a menudo basta con tener una respuesta más rápida con una alta [[probabilidad]] (aunque no segura) de ser cierta. Se puede comprobar rápidamente la primalidad de un número relativamente grande mediante [[test de primalidad|tests de primalidad]] probabilísticos. Estos tests suelen tomar un número aleatorio llamado "testigo" e introducirlo en una fórmula junto con el número potencialmente primo ''n''. Después de varias iteraciones, se resuelve que ''n'' es "definitivamente compuesto" o bien "probablemente primo". Estos últimos números pueden ser primos o bien [[pseudoprimo]]s (números compuestos que pasan el test de primalidad). Algunos de estos tests no son perfectos: puede haber números compuestos que el test considere "probablemente primos" independientemente del testigo utilizado. Esos números reciben el nombre de pseudoprimos absolutos para ese test. Por ejemplo, los [[números de Carmichael]] son números compuestos, pero el [[test de primalidad de Fermat|test de Fermat]] los evalúa como probablemente primos. Sin embargo, los tests probabilísticos más utilizados, como el [[test de primalidad de Miller-Rabin|test de Miller-Rabin]] o el obsoleto [[test de primalidad de Solovay-Strassen|test de Solovay-Strassen]], superado por el anterior, no tienen este inconveniente, aun siendo igualmente tests probabilísticos.

Algunos tests probabilísticos podrían pasar a ser determinísticos y algunos tests pueden mejorar su tiempo de ejecución si se verifican algunas hipótesis matemáticas. Por ejemplo, si se verifica la [[hipótesis generalizada de Riemann]], se puede emplear una versión determinística del test de Miller-Rabin, y el [[test de primalidad por curvas elípticas]] podría mejorar notablemente su tiempo de ejecución si se verificaran algunas hipótesis de teoría analítica de números.

=== Algoritmos de factorización ===
Un algoritmo de factorización es un [[algoritmo]] que separa uno a uno los factores primos de un número. Los algoritmos de factorización pueden funcionar también a modo de tests de primalidad, pero en general tienen un tiempo de ejecución menos ventajoso. Por ejemplo, se puede modificar el algoritmo de división por tentativa de forma que no se detenga cuando se obtenga una división exacta, sino que siga realizando nuevas divisiones, y no sobre el número original, sino sobre el cociente obtenido. Después de la división por tentativa, los métodos más antiguos que se conocen son el [[método de factorización de Fermat|método de Fermat]], que se basa en las diferencias entre [[cuadrado (aritmética)|cuadrados]] y que es especialmente eficaz cuando ''n'' es el producto de dos números primos próximos entre sí, y el [[método de factorización de Euler|método de Euler]], que se basa en la representación de ''n'' como [[suma de dos cuadrados]] de dos formas distintas.

Más recientemente, se han elaborado algoritmos basados en una gran variedad de técnicas, como las [[fracción continua|fracciones continuas]] o las [[curva elíptica|curvas elípticas]], aunque algunos son mejoras de métodos anteriores (la [[criba cuadrática]], por ejemplo, se basa en una mejora del método de Fermat y posee complejidad computacional subexponencial sobre el número de cifras de ''n''). Otros, como el [[método rho de Pollard]], son probabilísticos, y no garantizan hallar los divisores de un número compuesto.

Hoy por hoy, el algoritmo determinístico más rápido de uso general es la ''[[criba general del cuerpo de números]]'' ('''GNFS''' por las siglas de su nombre en inglés: ''General number field sieve''), que también posee complejidad computacional subexponencial sobre el número de cifras de ''n''.<ref>{{Cita web |idioma=inglés |url=http://mathworld.wolfram.com/NumberFieldSieve.html |autor=Eric W. Weisstein |título=Number Field Sieve |fechaacceso=31 de mayo de 2009}}</ref> Se ha propuesto un algoritmo cuyo tiempo de ejecución es polinómico sobre el número de cifras de ''n'' (el [[algoritmo de Shor]]), pero requiere ser ejecutado en un [[ordenador cuántico]], ya que su simulación en un ordenador normal requiere un tiempo exponencial. No se conocen algoritmos para factorizar en una computadora tradicional en tiempo polinómico y tampoco se demostró que esto sea imposible.

=== Fórmulas que solo generasen números primos ===
{{VT|Fórmula de los números primos}}

A lo largo de la historia, se han buscado numerosas [[fórmula de los números primos|fórmulas]] para generar los números primos. El nivel más alto de exigencia para una fórmula así sería que asociara a cada número natural ''n'' el ''n''-ésimo número primo. De forma más indulgente, se puede pedir una función ''f'' inyectiva que asocie a cada número natural ''n'' un número primo de tal forma que cada uno de los valores tomados aparezca solo una vez.

Además, se exige que la función se pueda aplicar, efectiva y eficazmente, en la práctica.<ref>Introducción del capítulo 3 del libro de Ribenboim ''The new book of prime number records''.</ref> Por ejemplo, el [[teorema de Wilson]] asegura que ''p'' es un número primo si y solo si (''p''-1)!≡-1 (mod ''p''). Otro ejemplo: la función f(''n'') = 2 + ( 2(''n''!) mod (''n''+1)) genera todos los números primos, solo los números primos, y solo el valor 2 se toma más de una vez. Sin embargo, ambas fórmulas se basan en el cálculo de un factorial, lo que las hace computacionalmente inviables.

En la búsqueda de estas funciones, se han investigado, notablemente, las funciones polinómicas. Cabe subrayar que ningún polinomio, aun en varias variables, devuelve solo valores primos.<ref name="pg_matijasevic">[http://primes.utm.edu/glossary/xpage/MatijasevicPoly.html Prime Glossary - ''Matijasevic's Polynomial''], accedido el 06-06-2009</ref> Por ejemplo, el polinomio en una variable ''f''(''n'') = ''n''² + ''n'' + 41, estudiada por Leonardo Euler, devuelve valores primos para ''n'' = 0, …, 39, sin embargo para n= 40, resulta <math> 40^2 +40 +41 = 41^2 </math> un número compuesto.<ref> I.S. Sominski «Método de inducción matemática» Editorial Mir, Moscú (1985) segunda edición</ref> Si el término constante vale cero, entonces el polinomio es múltiplo de ''n'', por lo que el polinomio es compuesto para valores compuestos de ''n''. En caso contrario, si ''c'' es el término constante, entonces ''f''(''cn'') es múltiplo de ''c'', por lo que si el polinomio no es constante, necesariamente deberá incluir valores compuestos.

Sin embargo, hay polinomios en varias variables cuyos valores positivos (cuando las variables recorren números naturales) son precisamente números primos. Un ejemplo, es este polinomio descubierto por Jones, Sato, Wada y Wiens en 1976:<ref name="pg_matijasevic" />

:<math>(1 - (w \cdot z + h + j - q)^2 - (2 \cdot n + p + q + z - e)^2 - (a^2 \cdot y^2 - y^2 + 1 - x^2)^2 \dots</math>
:<math> - (e^3 \cdot (e + 2) \cdot (a + 1)^2 + 1 - o^2)^2 - (16 \cdot (k + 1)^3 \cdot (k + 2) \cdot (n + 1)^2 + 1 - f^2)^2 \dots</math>
:<math> - (((a + u^2 \cdot (u^2 - a))^2 - 1) \cdot (n + 4 \cdot d \cdot y)^2 + 1 - (x + c \cdot u)^2)^2 - (a \cdot i + k + 1 - l - i)^2 \dots</math>
:<math> - ((g \cdot k + 2 \cdot g + k + 1) \cdot (h + j) + h - z)^2 - (16 \cdot r^2 \cdot y^4 \cdot (a^2 - 1) + 1 - u^2)^2 \dots</math>
:<math> - (p - m + l \cdot (a - n - 1) + b \cdot (2 \cdot a \cdot n + 2 \cdot a - n^2 - 2 \cdot n - 2))^2 - (z - p \cdot m + p \cdot l \cdot a - p^2l + t \cdot (2 \cdot a \cdot p - p^2 - 1))^2 \dots</math>
:<math> - (q - x + y \cdot (a - p - 1) + s \cdot (2 \cdot a \cdot p + 2 \cdot a - p^2 - 2 \cdot p - 2))^2 - (a^2 \cdot l^2 - l^2 + 1 - m^2)^2 - (n + l + v - y)^2) \cdot (k + 2)</math>

Al igual que ocurre con las fórmulas con factoriales, este polinomio no es práctico de calcular, ya que, aunque los valores positivos que toma son todos primos, prácticamente no devuelve otra cosa que valores negativos cuando se hacen variar las variables ''a'' a ''z'' de 0 a infinito.

Otro enfoque al problema de encontrar una función que solo genere números primos viene dado a partir del [[teorema de Mills]], que indica que existe una constante θ tal que
:<math>\lfloor \theta^{3^n}\rfloor</math>

es siempre un número primo, donde <math>\lfloor \rfloor</math> es la [[función parte entera|función piso]].<ref> W. H. Mills, ''A prime-representing function'' (1947) (en inglés)</ref> Todavía no se conoce ninguna fórmula para calcular la constante de Mills, y las aproximaciones que se emplean en la actualidad se basa en la sucesión de los así llamados números primos de Mills (los números primos generados mediante esta fórmula), que no pueden ser obtenidos rigurosamente, sino solo de manera probabilística, suponiendo cierta la [[hipótesis de Riemann]].

== Clases de números primos ==
De mayor interés son otras fórmulas que, aunque no solo generen números primos, son más rápidas de implementar, sobre todo si existe un algoritmo especializado que permita calcular rápidamente la primalidad de los valores que van tomando. A partir de estas fórmulas se obtienen subconjuntos relativamente pequeños del conjunto de los números primos, que suelen recibir un nombre colectivo.

=== Primos primoriales y primos factoriales ===
{{VT|Número primo primorial|número primo factorial}}
Los [[número primo primorial|números primos primoriales]], directamente relacionados con la demostración euclidiana de la infinitud de los números primos, son los de la forma ''p'' = ''n''#&nbsp;±&nbsp;1 para algún número natural ''n'', donde [[primorial|''n''#]] es igual al producto 2&nbsp;·&nbsp;3&nbsp;·&nbsp;5&nbsp;·&nbsp;7&nbsp;·&nbsp;11&nbsp;·&nbsp;… de todos los primos ≤&nbsp;n. Asimismo, un número primo se dice [[número primo factorial|primo factorial]] si es de la forma [[factorial|''n''!]]&nbsp;±&nbsp;1. Los primeros primos factoriales son:
: ''n''!&nbsp;−&nbsp;1 es primo para ''n'' = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, 324, …<ref>{{OEIS|A002982}}</ref>
: ''n''!&nbsp;+&nbsp;1 es primo para ''n'' = 0, 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, 320, …<ref>{{OEIS|A002981}}</ref>

=== Números primos de Fermat ===
{{VT|Número de Fermat}}
[[Archivo:Pentagon construct.gif|Construcción de un [[pentágono]] regular. 5 es un [[número primo de Fermat]].|thumb]]
Los [[Número primo de Fermat|números de Fermat]], ligados a la construcción de [[polígono regular|polígonos regulares]] con [[regla y compás]], son los números de la forma <math>F_n=2^{2^n} + 1</math>, con ''n'' natural. Los únicos números primos de Fermat que se conocen hasta la fecha son los cinco que ya conocía el propio Fermat, correspondientes a ''n'' = 0, 1, 2, 3 y 4, mientras que para valores de ''n'' entre 5 y 32 estos números son compuestos.<ref name="Keller">{{Cita web |apellido=Keller |nombre=Wilfrid |año=2009 |título=Fermat factoring status |url=http://www.prothsearch.net/fermat.html |fechaacceso=1 de junio de 2009 |urlarchivo=https://web.archive.org/web/20160210152415/http://www.prothsearch.net/fermat.html |fechaarchivo=10 de febrero de 2016 }}</ref>

Para determinar su primalidad, existe un test especializado cuyo [[tiempo de ejecución polinómico|tiempo de ejecución es polinómico]]: el [[test de Pépin]]. Sin embargo, los propios números de Fermat crecen tan rápidamente que solo se lo ha podido aplicar para valores de ''n'' pequeños. En 1999 se lo aplicó para ''n'' = 24. Para determinar el carácter de otros números de Fermat mayores se utiliza el [[División por tentativa|método de divisiones sucesivas]] y de esa manera a fecha de junio de 2009 se conocen 241 números de Fermat compuestos, aunque en la mayoría de los casos se desconozca su factorización completa.<ref name="Keller" />

=== Números primos de Mersenne ===
{{VT|Número primo de Mersenne}}
Los [[Número primo de Mersenne|números de Mersenne]] son los de forma M<sub>''p''</sub> = 2<sup>''p''</sup> – 1, donde ''p'' es primo.<ref>{{Cita web |url=http://gaussianos.com/todo-numero-de-mersenne-con-exponente-compuesto-es-tambien-compuesto/
 |título=Todo número de Mersenne con exponente compuesto es también compuesto
 |fechaacceso=7 de junio de 2009

 |autor=DiAmOnD
 |año=2008
}}. Por [[demostración por contraposición|contraposición]], se deduce que, para buscar números primos de Mersenne, basta con buscar entre los números de Mersenne con exponente primo.</ref> Los mayores números primos conocidos son generalmente de esta forma, ya que existe un test de primalidad muy eficaz, el [[test de primalidad de Lucas-Lehmer|test de Lucas-Lehmer]], para determinar si un número de Mersenne es primo o no.

Actualmente, el mayor número primo que se conoce es ''M''<sub>136.279.841</sub> = 2<sup>136.279.841</sup> - 1, que tiene 41 024 320 cifras en el sistema decimal. Se trata cronológicamente del {{Ord|52.|o}} número primo de Mersenne conocido y su descubrimiento se anunció el 21 de octubre de 2024<ref name="GIMPS-2024">{{cite web |title=GIMPS Project Discovers Largest Known Prime Number: 2<sup>136.279.841</sup>-1 |url=https://www.mersenne.org/primes/?press=M136279841 |date=21 de octubre de 2024 |work=Mersenne Research, Inc. |accessdate=26 de diciembre de 2024 }}</ref> gracias al proyecto de [[computación distribuida]] «[[Great Internet Mersenne Prime Search]]» (GIMPS).

=== Otras clases de números primos ===
Existen literalmente decenas de ''apellidos'' que se pueden añadir al concepto de ''número primo'' para referirse a un subconjunto que cumple alguna propiedad concreta. Por ejemplo, los [[Número primo pitagórico|números primos pitagóricos]] son los que se pueden expresar en la forma 4''n''+1. Dicho de otra forma, se trata de los números primos cuyo resto al dividirlos entre 4 es 1. Otro ejemplo es el de los [[Número primo de Wieferich|números primos de Wieferich]], que son aquellos números primos ''p'' tales que ''p''<sup>2</sup> divide a 2<sup>''p''-1</sup> - 1.

Algunas de estas propiedades se refieren a una relación concreta con otro número primo:
* [[Números primos gemelos]]: ''p'' y ''p+2'' lo son si son los dos primos.
* [[Número primo de Sophie Germain]]: dado ''p'' primo, es de Sophie Germain si 2''p'' + 1 también es primo. Una sucesión de números ''p''<sub>1</sub>,''p''<sub>2</sub>,''p''<sub>3</sub>,··· ,''p''<sub>''n''</sub> todos ellos primos, tales que ''p''<sub>''i''+1</sub>=2''p''<sub>''i''</sub>+1 para todo ''i'' ∈ {1,2,···,n-1 }, se denomina [[cadena de Cunningham|cadena (completa) de Cunningham de primera especie]], y cumple por definición que cada uno de los términos, salvo el último, es un número primo de Sophie Germain. Se cree que para todo ''n'' natural existen infinitas cadenas de Cunningham de longitud ''n'',<ref>{{Cita web
 |url          = http://www.gang.umass.edu/~franz/teaching/group1.pdf
 |título      = Prime Numbers and the Riemann Hypothesis
 |fechaacceso  = 7 de junio de 2009
 |autor        = Nicholas Anderson, Andrew J. Havens, Brian Hydefrost, Sean Murphy y Steve Sarasin
 |páginas     = 6
 |urlarchivo   = https://web.archive.org/web/20100615035617/http://www.gang.umass.edu/~franz/teaching/group1.pdf
 |fechaarchivo = 15 de junio de 2010
}}</ref> aunque hasta la fecha nadie ha proporcionado prueba de que dicha afirmación sea cierta.
* [[Número primo de Wagstaff]]: ''p'' lo es si <math>\textstyle p={{2^q+1}\over 3}</math>, donde ''q'' es otro número primo.<ref>{{Cita web
 |url          = http://www.research.att.com/~njas/sequences/A000979
 |título      = A000979. Wagstaff primes.
 |fechaacceso  = 23 de abril de 2010
 |autor        = The On-Line Encyclopedia of Integer Sequences!
 |urlarchivo   = https://web.archive.org/web/20100618082417/http://www.research.att.com/~njas/sequences/A000979
 |fechaarchivo = 18 de junio de 2010
}}</ref><ref>{{MathWorld|WagstaffPrime|Wagstaff Prime}}</ref>

También se les da nombres especiales a algunas clases de primos que dependen de la base de numeración empleada o de la forma de escribir los dígitos, y no de una fórmula matemática. Es el caso de los [[omirp|números ''somirp'']] (''primos'' al revés), que son aquellos números primos tales que el número obtenido al invertir el orden de sus cifras también es primo. También es el caso de los [[número primo repunit|números primos repunit]], que son aquellos números primos que son concatenación de unos. Si, en lugar de considerarse el [[sistema de numeración decimal]] se considera el [[sistema de numeración binario|binario]], se obtiene otro conjunto distinto de números primos repunit que, además, coincide con el de los números primos de Mersenne. Finalmente, los [[número primo triádico|números primos triádicos]] son aquellos números que son primos, [[número capicúa|capicúas]] y simétricos respecto de una recta horizontal.

El que se le dé un nombre a una clase de números primos con una definición precisa no significa que se conozca algún número primo que sea de esa clase. Por ejemplo, no se conoce hasta el momento ningún [[número primo de Wall-Sun-Sun]], pero su relevancia radica en que en 1992, antes de la demostración de Wiles del [[último teorema de Fermat]], se descubrió que la falsedad del teorema para un número primo ''p'' dado implicaba que ''p'' era un número primo de Wall-Sun-Sun. Esto hizo que, durante un tiempo, la búsqueda de números primos de esta clase fuera también la búsqueda de un contraejemplo del último teorema de Fermat.<ref>{{Prime Pages|id=WallSunSunPrime|título=Wall-Sun-Sun prime|fechaacceso= 6 de junio de 2009}}</ref>

===Cuadro resumen===

{|class="wikitable" width=100% style="font-size:85%;"
||
{|width=100%
|bgcolor=#ccccff style="font-size:125%;"|<center>'''Clases de números primos'''</center>
|}
|-
||
{|width=100%
|-
|bgcolor=#ccccff style="text-align:right; font-weight:550;" width=15%|Por fórmula&nbsp;&nbsp;&nbsp;
|bgcolor="white" width=85%|
• [[Número de Fermat|Fermat ({{math|size=90%|1=2<sup>2<sup>''n''</sup></sup>&nbsp;+&nbsp;1}})]] • [[Número primo de Mersenne|Mersenne ({{math|size=90%|1=2<sup>''p''</sup>&nbsp;−&nbsp;1}})]] • [[Número doble de Mersenne|Mersenne doble ({{math|size=90%|1=2<sup>2<sup>''p''</sup>-1</sup>&nbsp;-&nbsp;1}})]] • [[Número primo de Wagstaff|Wagstaff  {{math|size=90%|1=(2<sup>''p''</sup>&nbsp;+&nbsp;1)/3}}]] • [[Número primo de Proth|Proth ({{math|size=90%|1=''k''·2<sup>''n''</sup>&nbsp;+&nbsp;1}})]] • [[Número primo factorial|Factorial ({{math|size=90%|1=''n''!&nbsp;±&nbsp;1}})]] • [[Número primo primorial|Primorial ({{math|size=90%|1=''p<sub>n</sub>''#&nbsp;±&nbsp;1}})]] • [[Número de Euclides|Euclides ({{math|size=90%|1=''p<sub>n</sub>''#&nbsp;+&nbsp;1}})]] • [[Número primo pitagórico|Pitagórico ({{math|size=90%|1=4''n''&nbsp;+&nbsp;1}})]] •&nbsp;[[Número primo de Pierpont|Pierpont ({{math|size=90%|1=2<sup>''m''</sup>·3<sup>''n''</sup>&nbsp;+&nbsp;1}})]] • [[Número primo cuártico|Cuártico ({{math|size=90%|1=''x''<sup>4</sup>&nbsp;+&nbsp;''y''<sup>4</sup>}})]] • [[Primo de Solinas|Solinas ({{math|size=90%|1=2<sup>''m''</sup>&nbsp;±&nbsp;2<sup>''n''</sup>&nbsp;±&nbsp;1}})]] • [[Número de Cullen|Cullen ({{math|size=90%|1=''n''·2<sup>''n''</sup>&nbsp;+&nbsp;1}})]] • [[Número de Woodall|Woodall ({{math|size=90%|1=''n''·2<sup>''n''</sup>&nbsp;-&nbsp;1}})]] • [[Número primo cúbico|Cúbico ({{math|size=90%|1=''x''<sup>3</sup>&nbsp;-&nbsp;''y''<sup>3</sup>)/(''x''&nbsp;-&nbsp;''y''}})]]   • [[Número de Leyland|Leyland ({{math|size=90%|1=''x<sup>y</sup>''&nbsp;+&nbsp;''y<sup>x</sup>''}})]] {{nowrap|• [[Número de Thabit|Thabit ({{math|size=90%|1=3·2<sup>''n''</sup>&nbsp;-&nbsp;1}})]]}} • [[Número primo de Williams|Williams ({{math|size=90%|1=(''b''-1)·''b''<sup>''n''</sup>&nbsp;-&nbsp;1}})]] • [[Constante de Mills|Mills (⌊A3n⌋)]]
|}

|-
||
{|width=100%
|-
|bgcolor=#ccccff style="text-align:right; font-weight:550;" width=15%|[[Primos en series enteras|En series de enteros]]&nbsp;&nbsp;&nbsp;
|bgcolor=#f7f7f7 width=85%|
• [[Número primo de Fibonacci|Fibonacci]] • [[Número de Lucas|Lucas]] • [[Número de Pell|Pell]] • [[Número primo de Newman-Shanks-Williams|Newman-Shanks-Williams]] • [[Número de Perrin|Perrin]] • [[Partición (teoría de números)|Particiones]] • [[Número de Bell|Bell]] • [[Número de Motzkin|Motzkin]]
|}

|-
||
{|width=100%
|-
|bgcolor=#ccccff style="text-align:right; font-weight:550;" width=15%|Por sus propiedades&nbsp;&nbsp;&nbsp;
|bgcolor="white" width=85%|
• [[Número primo de Wieferich|Wieferich]] ([[par de Wieferich|par]]) • [[Número primo de Wall-Sun-Sun|Wall-Sun-Sun]] • [[Número primo de Wolstenholme|Wolstenholme]] • [[Número primo de Wilson|Wilson]] • [[Número de la suerte|De la suerte]] • [[Número afortunado|Afortunado]] • [[Número primo de Ramanujan|Ramanujan]] • [[Número primo de Pillai|Pillai]] • [[Primo regular|Regular]] • [[Número primo fuerte|Fuerte]] • [[Número primo de Stern|Stern]] • [[Número primo supersingular (teoría algebraica de números)|Supersingular (curva elíptica)]] •&nbsp;[[Número primo supersingular (teoría moonshine)|Supersingular (teoría moonshine)]] • [[Número primo bueno|Bueno]] • [[Número superprimo|Superprimo]] • [[Número primo de Higgs|Higgs]] • [[Número altamente cototiente|Altamente cototiente]]
|}

|-
||
{|width=100%
|-
|bgcolor=#ccccff style="text-align:right; font-weight:550;" width=15%|[[Base (aritmética)|Base]]-dependiente&nbsp;&nbsp;&nbsp;
|bgcolor=#f7f7f7 width=85%|
• [[Número primo palindrómico|Palindrómico]] • [[Omirp]] • [[Repunit|Repunit  {{math|size=90%|1=(10<sup>''n''</sup>&nbsp;-&nbsp;1)/9}}]] • [[Número primo permutable|Permutable]] • [[Número primo circular|Circular]] • [[Número primo truncable|Truncable]] • [[Número primo mínimo (matemáticas recreativas)|Mínimo]] • [[Número primo delicado|Delicado]] • [[Número primo primitivo|Primitivo]] • [[Número primo largo|Largo]] • [[Número primo único|Único]] • [[Número feliz|Feliz]] • [[Autonúmero]] • [[Número primo de Smarandache-Wellin|Smarandache-Wellin]] •&nbsp;[[Número primo estrobogramático|Estrobogramático]] • [[Número primo diédrico|Diédrico]] • [[Número primo tetrádico|Tetrádico]]
|}

|-
||
{|width=100%
|-
|bgcolor=#ccccff style="text-align:right; font-weight:550;" width=15%|Por patrones de aparición&nbsp;&nbsp;&nbsp;
|bgcolor="white" width=85%|
• [[Número primo gemelo|Gemelos ({{math|size=90%|1=''p'', ''p''&nbsp;+&nbsp;2}})]] • [[Cadena bigemela|Cadena bigemela ({{math|size=90%|1=''n''&nbsp;-&nbsp;1, ''n''&nbsp;+&nbsp;1, 2''n''&nbsp;-&nbsp;1, 2''n''&nbsp;+&nbsp;1, …}})]] • [[Triplete primo|Triplete ({{math|size=90%|1=''p'', ''p''&nbsp;+&nbsp;2 or ''p''&nbsp;+&nbsp;4, ''p''&nbsp;+&nbsp;6}})]] • [[Cuadruplete primo|Cuadruplete ({{math|size=90%|1=''p'', ''p''&nbsp;+&nbsp;2, ''p''&nbsp;+&nbsp;6, ''p''&nbsp;+&nbsp;8}})]] • [[k-tupla de números primos|''k''-tupla]] • [[Número primo primo|Primo ''primo'' ({{math|size=90%|1=''p'', ''p''&nbsp;+&nbsp;4}})]] {{nowrap|•&nbsp;[[Número primo sexy|Sexy ({{math|size=90%|1=''p'', ''p''&nbsp;+&nbsp;6}})]]}} • [[Número primo de Chen|Chen]] • [[Número primo de Sophie Germain|Sophie Germain/seguro ({{math|size=90%|1=''p'', 2''p''&nbsp;+&nbsp;1}})]] • [[Cadena de Cunningham|Cunningham ({{math|size=90%|1=''p'', 2''p''&nbsp;±&nbsp;1, 4''p''&nbsp;±&nbsp;3, 8''p''&nbsp;±&nbsp;7, ...}})]] • [[Números primos en progresión aritmética|Progresión aritmética ({{math|size=90%|1=''p''&nbsp;+&nbsp;''a·n'', ''n''&nbsp;=&nbsp;0,&nbsp;1,&nbsp;2,&nbsp;3,&nbsp;...}})]] {{nowrap|• [[Número primo equilibrado|Equilibrado ({{math|size=90%|1=''p''&nbsp;-&nbsp;''n'', ''p'', ''p''&nbsp;+&nbsp;''n'' consecutivos}})]]}}
|}

|-
||
{|width=100%
|-
|bgcolor=#ccccff style="text-align:right; font-weight:550;" width=15%|Por tamaño&nbsp;&nbsp;&nbsp;
|bgcolor=#f7f7f7 width=85%|
• [[Megaprimo|Megaprimo <small>(1.000.000+ dígitos)</small>]] • [[Mayor número primo conocido|Mayor conocido]] 
|}

|-
||
{|width=100%
|-
|bgcolor=#ccccff style="text-align:right; font-weight:550;" width=15%|[[Números complejos]]&nbsp;&nbsp;&nbsp;
|bgcolor="white" width=85%|
• [[Primo de Eisenstein|Eisenstein]] • [[Entero gaussiano|Gaussiano]]
|}

|-
||
{|width=100%
|-
|bgcolor=#ccccff style="text-align:right; font-weight:550;" width=15%|[[Número compuesto|Números compuestos]]&nbsp;&nbsp;&nbsp;
|bgcolor=#f7f7f7 width=85%|
• [[Número pseudoprimo|Números pseudoprimos]] ([[Número pseudoprimo de Catalan|• Catalán]]) • [[Número pseudoprimo elíptico|Elíptico]] • [[Número pseudoprimo de Euler|Euler]] • [[Número pseudoprimo de Euler-Jacobi|Euler-Jacobi]] • [[Número pseudoprimo de Fermat|Fermat]] • [[Número pseudoprimo de Frobenius|Frobenius]] • [[Número pseudoprimo de Lucas|Lucas]] • [[Número pseudoprimo de Somer-Lucas|Somer-Lucas]] • [[Número pseudoprimo fuerte|(Fuerte]]) • [[Número de Carmichael|Carmichael]] • [[Número casi primo|Casi primo]] • [[Número semiprimo|Semiprimo]] • [[Número interprimo|Interprimo]] •&nbsp;[[Número pernicioso|Pernicioso]]
|}

|-
||
{|width=100%
|-
|bgcolor=#ccccff style="text-align:right; font-weight:550;" width=15%|Otros tipos&nbsp;&nbsp;&nbsp;
|bgcolor="white" width=85%|
• [[Probable primo]] • [[Número primo de grado industrial]] • [[Número ilegal]] • [[Fórmula de los números primos]] • [[Diferencia entre dos números primos consecutivos]]
|}
|}

== Conjeturas ==
Existen numerosas preguntas abiertas acerca de los números primos. Muchas de ellas son problemas bien antiguos, y una de las más significativas es la hipótesis de Riemann, varias veces mencionada en este artículo como una conjetura que, de ser cierta, permitiría conocer numerosos resultados relevantes en diversos campos de las matemáticas.

=== Hipótesis de Riemann ===
{{VT|Hipótesis de Riemann}}
Para entender la hipótesis de Riemann, una conjetura enunciada en 1859 pero que, hasta la fecha ({{CURRENTYEAR}}), sigue sin resolverse, es necesario entender la [[función zeta de Riemann]]. Sea <math>s</math> un [[número complejo]] con [[parte real]] mayor que 1. Entonces,
{{Ecuación|
<math>\zeta(s)=\sum_{n=1}^\infin \frac{1}{n^s} = \prod_{p} \frac{1}{1-p^{-s}}.</math>
||left}}
La segunda igualdad es una consecuencia del [[teorema fundamental de la aritmética]], y muestra que la función zeta está íntimamente relacionada con los números primos.

Existen dos tipos de ceros de la función zeta, es decir, valores ''s'' para los cuales ζ(''s'') = 0: los ''triviales'', que son ''s''=-2, ''s''=-4, ''s''=-6, etc., (los enteros pares negativos) y los ''no triviales'', que son aquellos ceros que no se encuentran en el eje real. Lo que indica la hipótesis de Riemann es que la parte real de todos los ceros no triviales es igual a 1/2.

La veracidad de la hipótesis implica una profunda conexión con los números primos, en esencia, en el caso de verificarse, dice que los números primos están distribuidos de la forma más regular posible. Desde un punto de vista «físico», dice ''grosso modo'' que las irregularidades en la distribución de los números primos solo proceden de ruido aleatorio. Desde un punto de vista matemático, dice que la distribución asintótica de los números primos (según el [[teorema de los números primos]], la proporción de primos menores que ''n'' es <math>\tfrac{1}{\ln(n)}</math>) también es cierta para intervalos mucho menores, con un error de aproximadamente la raíz cuadrada de ''n'' (para intervalos próximos a ''n''). Está ampliamente extendido en la comunidad matemática que la hipótesis sea cierta. En concreto, la presunción más simple es que los números primos no deberían tener irregularidades significativas en su distribución sin una buena razón.<ref>{{Cita web
 |url          = http://www.claymath.org/millennium/Riemann_Hypothesis/riemann.pdf
 |título      = The Riemann hypothesis
 |fechaacceso  = 6 de junio de 2009
 |autor        = Bombieri, Enrico
 |enlaceautor  = Enrico Bombieri
 |año         = 2000
 |editorial    = Clay Mathematics Institute
 |idioma       = Inglés
 |urlarchivo   = https://web.archive.org/web/20090327181245/http://www.claymath.org/millennium/Riemann_Hypothesis/riemann.pdf
 |fechaarchivo = 27 de marzo de 2009
}}</ref>

=== Otras conjeturas ===
==== Infinitud de ciertos tipos de números primos ====
Muchas conjeturas tratan sobre si hay infinitos números primos de una determinada forma. Así, se conjetura que hay infinitos [[número primo de Fibonacci|números primos de Fibonacci]]<ref>{{Prime Pages|id=48|título=Lucas Number|clase=top20|fechaacceso= 1 de junio de 2009}}</ref> e infinitos [[número primo de Mersenne|primos de Mersenne]], pero solo un número finito de [[número primo de Fermat|primos de Fermat]].<ref>Por ejemplo, véase {{Obra citada |apellido=Guy |nombre=Richard K. |título=Unsolved Problems in Number Theory |editorial=Springer-Verlag |año=1981}}, problema A3, pp. 7–8.</ref> No se sabe si hay infinitos [[número primo de Euclides|números primos de Euclides]].

==== Distribución de los números primos ====
También hay numerosas conjeturas que se ocupan de determinadas propiedades de la distribución de los números primos. Así, la [[conjetura de los números primos gemelos]] enuncia que hay infinitos [[números primos gemelos]], que son pares de primos cuya diferencia es de 2. La [[conjetura de Polignac]] es una versión más general y más fuerte de la anterior, ya que enuncia que, para cada entero positivo ''n'', hay infinitos pares de primos consecutivos que difieren en 2''n''. A su vez, una versión más débil de la conjetura de Polignac dice que todo [[número par]] es la diferencia de dos números primos.

Asimismo, se conjetura la infinidad de los primos de la forma ''n''<sup>2</sup> + 1. Según la [[conjetura de Brocard]], entre los cuadrados de primos consecutivos mayores que 2 existen siempre al menos cuatro números primos. La [[conjetura de Legendre]] establece que, para cada ''n'' natural, existe un número primo entre ''n''<sup>2</sup> y (''n''+1)<sup>2</sup>. Finalmente, la [[conjetura de Cramér]], cuya veracidad implicaría la de Legendre, dice que:
{{ecuación|
<math>\limsup_{n\rightarrow\infty} \frac{p_{n+1}-p_n}{(\log p_n)^2} = 1</math>
||left}}

==== Teoría aditiva de números ====
Otras conjeturas relacionan algunas [[teoría de números aditiva|propiedades aditivas]] de los números con los números primos. Así, la [[conjetura de Goldbach]] dice que todo número par mayor que 2 se puede escribir como suma de dos números primos, aunque también existe una [[conjetura débil de Goldbach|versión más débil]] de la misma conjetura según la cual todo número impar mayor que 5 se puede escribir como suma de tres números primos. El matemático [[China|chino]] [[Chen Jingrun]] demostró, en 1966, que en efecto, todo número par suficientemente grande puede expresarse como suma de dos primos o como la suma de un primo y de un número que es el producto de dos primos. ([[Número semiprimo|"''semi''-primo"]]).<ref name = 50COSAS>{{Cita libro |título=50 cosas que hay que saber sobre matemáticas |autor=Tony Crilly |editorial=Ed. Ariel |isbn = 978-987-1496-09-9|año=2011 }}</ref><!-- fata referencias 
Así mismo, teniendo como valor fundamental que un número compuesto no es sino la suma de un número primo repetidas veces, resultando múltiplo de sí mismo o a su vez de otro número primo que intervenga en la adición, cabe representar que los números primos pueden formarse de manera aditiva en una línea de adición ''+2n'' que tenga como partida el primer número primo, el número 3, lo que es una única línea aditiva que responda a ''3+2n''. De esta manera, al sumar al número 3 cualquier número par que no sea múltiplo de 3 tiene como resultado un número impar que no es múltiplo de 3; en el caso del número 5 (3+2*1), el número 7 (3+2*2), el número 11 (3+2*4) y el número 13 (3+2*5) ninguno de los valores de ''n'' es múltiplo de 3, de ahí que el resultado no sea divisible ni entre el número 3 ni entre ninguno de los números anteriormente obtenidos dado que el número par que interviene en la adición a 3 proviene de un múltiplo de 2 que jamás dispondrá un resultado múltiplo de 3, o proviene valor ''n'' inferior a cualquiera de los resultados impares obtenidos por lo que tampoco pueden ser múltiplos de los mismos. En lo sucesivo y dada la particularidad de que cualquier número par múltiplo de un número primo deja de ser compuesto del mismo si se le suma la unidad o un número primo distinto (demostración de primos infinitos de Euclides), el primer resultado que proviene de sumar a 3 un número par igual o mayor a un primo anterior también es primo, o sea el número 13 (3+2*5) y así genéricamente como el 17 (3+2*7), el 19 (3+2*8), el 23 (3+2*10 que a su vez es 3+2[5*2]), el 29 (3+2*13), el 31 (3+2*14 que a su vez es 3+2*[7*2]), 37 (3+2*17), 41 (3+2*19), 43 (3+2*20 que a su vez es 3+2*[5*(2*2)]), 47 (3+2*22 que a su vez es 3+2*[11*2]) y es el en número 49 cuando se puede establecer claramente la pauta que continuarán en la línea aditiva ''3+2n'' los números múltiplos de números primos distintos que 3, la cuál hasta esta cifra (49) permanecía “escondida” ante la evidencia que supone los números impares múltiplos de 3 (''3+2n(3)'') y que todo número cuya unidad sea 5 es múltiplo de este número primo en cuestión.

En los casos del número 9 y número 15, ambos múltiplos de 3, se da el caso que el múltiplo que interviene en la adición en sí mismo múltiplo de 3 (3+2*3 y 3+2*6), teniendo este último una particularidad que viene a evidenciar la relación que guardan los números primos entre sí si se les posiciona en una única línea aditiva ''3+2n''. Todos los múltiplos de 5, hasta el 45 cumplen la singularidad ''3+2[(5n)+1]'', como es el ya mencionado caso del número 15 (3+2*[5+1]) y el 45 (3+2*[(5*4)+1). La singularidad de ''2[(5n)+1]'' se repite en el primer múltiplo que no es ni compuesto de 3 ni de 5. El número 49, que como todos los cuadrados de un número primo es el primer número impar producto de un número primo que no es divisible por todos los primos anteriores, responde a 3+2(23) por lo que sin tener en cuenta todo lo anteriormente mencionado el doble de 23 no guarda ninguna relación con el número 3, pero sin embargo si atendemos a una descomposición más detallada obtenemos que 49 es el resultado de 3+2[(7*3)+2] y es aquí donde se vislumbra de nuevo la singularidad que relaciona todos los compuestos de otros números primos distintos al número 3 con el mismo número 3 en una única línea de adición ''3+2n''. Dicha singularidad responde a que, en los casos anteriormente mencionados, siempre resultan múltiplos de 5 cuando los números pares que se sumen a 3 provienen de un múltiplo de 5 más 1 (''2[(5n)+1]'') y serán múltiplos de 7 cuando los números pares que se sumen a 3 provengan de un múltiplo de 7 más 2 (''2[(7n)+2]''). Lo que significa dicha singularidad (''2[(pr*n)+ps]''), que se denomina ''ps'' de posición, es la cantidad de números pares (en unidades) que existen entre un número primo y el número 3 (o sea, su “posición” en la línea de adición ''3+2n'').

Por lo que, por la relación que existe de la demostración de Euclides con la particularidad de que cualquier número par múltiplo de un número primo deja de ser compuesto del mismo si se le suma la unidad o un número primo distinto, en una única línea de adición ''3+2n'' que tiene como inicio el número 3, resultarán números primos todas aquellas sumas que en las que no intervenga un número par múltiplo de 3 (''3+2(3n)'') y así mismo también resultarán números primos todas aquellas sumas en las que no intervenga un número par múltiplo de otro número primo distinto a 3 al que se le ha sumado también su "posición" en la línea aditiva ''3+2n'', que se obtiene de la diferencia de números pares (en unidades) que existen entre dicho número primo y el número 3 (o sea, siempre que el número par que se suma al número 3 no sea resultado de ''2[(pr*n)+ps]'' siendo ''ps=(pr-3)/2''), siendo este valor de posición (la diferencia de números pares, en unidades, existentes entre un número primo y 3) el indicador de la posición de dicho número primo en la línea única de adición ''3+2n''.
-->

=== Los cuatro problemas de Landau ===
En 1912, [[Edmund Landau|Landau]] estableció en el [[Congreso Internacional de Matemáticos|Quinto Congreso Internacional de Matemáticos]] de Cambridge una lista de cuatro de los problemas ya mencionados sobre números primos, que se conocen como los [[problemas de Landau]]. Ninguno de ellos está resuelto hasta la fecha. Se trata de la conjetura de Goldbach, la de los números primos gemelos, la de Legendre y la de los primos de la forma ''n''<sup>2</sup> + 1.<ref>[http://mathworld.wolfram.com/LandausProblems.html Mathworld - Landau's Problems] (en inglés)</ref>

== Generalización del concepto de número primo ==
El concepto de número primo es tan importante que se ha visto generalizado de varias maneras en diversas ramas de las matemáticas.

=== Elementos primos en un anillo ===
[[Archivo:Gaussian primes.svg|thumb|250px|Representación de los primos gaussianos de norma menor o igual a 500. Los primos gaussianos son, por definición, los [[entero gaussiano|enteros gaussianos]] que son primos.]]
Se pueden definir los [[elemento primo|elementos primos]] y los [[elemento irreducible|elementos irreducibles]] en cualquier [[dominio de integridad]].<ref> {{Cita web
 |url          = http://www.iesmurgi.org/matematicas/materiales/numeros/node18.html
 |título      = Números algebraicos
 |fechaacceso  = 7 de junio de 2009
 |año         = 2004
 |urlarchivo   = https://web.archive.org/web/20090529023652/http://www.iesmurgi.org/matematicas/materiales/numeros/node18.html
 |fechaarchivo = 29 de mayo de 2009
}}</ref>
En cualquier [[dominio de factorización única]], como por ejemplo, el anillo <math>\mathbb{Z}</math> de los enteros, el conjunto de elementos primos equivale al conjunto de los elementos irreducibles, que en <math>\mathbb{Z}</math> es {…, −11, −7, −5, −3, −2, 2, 3, 5, 7, 11, …}.

Considérense por ejemplo los [[entero gaussiano|enteros gaussianos]] <math>\mathbb{Z}[i]</math>, es decir, los [[número complejo|números complejos]] de la forma ''a''+''bi'' con ''a'', ''b'' ∈ <math>\mathbb{Z}</math>. Este es un dominio de integridad, y sus elementos primos son los [[entero gaussiano|primos gaussianos]]. Cabe destacar que el 2 ''no'' es un primo gaussiano, porque admite factorización como producto de los primos gaussianos (1+''i'') y (1-''i''). Sin embargo, el elemento 3 sí es primo en los enteros gaussianos, pero no lo es en otro dominio entero. En general, los primos racionales (es decir, los elementos primos del anillo <math>\mathbb{Z}</math>) de la forma 4''k''+3 son primos gaussianos, pero no lo son aquellos de la forma 4''k''+1.

=== Ideales primos ===
En [[teoría de anillos]], un [[ideal (teoría de anillos)|ideal]] ''I'' es un subconjunto de un [[anillo (matemática)|anillo]] ''A'' tal que
* si ''i'', ''j'' ∈ ''I'', entonces la suma ''i'' + ''j'' pertenece a ''I''
* y si ''x'' ∈ ''A'', ''i'' ∈ ''I'', entonces los productos ''a'' × ''i'', ''i'' × ''a'' pertenecen a ''I''.

Un [[ideal primo]] se define entonces como un ideal que cumple también que:
* para cualquier par de elementos ''a'', ''b'' del anillo ''A'' tales que su producto ''a'' × ''b'' pertenece a ''I'', entonces, al menos uno de los dos elementos, ''a'' o ''b'', está en ''I''.
* ''I'' no es el anillo ''A'' entero.

Los ideales primos son una herramienta relevante en [[álgebra conmutativa]], [[teoría algebraica de números]] y [[geometría algebraica]]. Los ideales primos del anillo de enteros son los ideales (0), (2), (3), (5), (7), (11), …

Un problema central en teoría algebraica de números es la manera en que se factorizan los ideales primos cuando se ven sometidos a una extensión de cuerpos.<!--A central problem in algebraic number theory is how a prime ideal factors when it is ''lifted'' to an extension field.--> En el ejemplo de los enteros gaussianos, (2) se ''ramifica'' en potencia de un primo (ya que <math>1+i</math> y <math>1-i</math> generan el mismo ideal primo), los ideales primos de la forma <math>4k+3</math> son ''inertes'' (mantienen su primalidad) y los de la forma <math>4k+1</math> pasan a ser producto de dos ideales primos distintos.

=== Primos en teoría de la valoración ===
En teoría algebraica de números surge otra generalización más. Dado un [[cuerpo (matemáticas)|cuerpo]] <math>\mathbb{K}</math>, reciben el nombre de [[valoración (matemáticas)|valoraciones]] sobre <math>\mathbb{K}</math> determinadas funciones de <math>\mathbb{K}</math> en <math>\mathbb{R}</math>. Cada una de estas valoraciones genera una [[cuerpo topológico|topología]] sobre <math>\mathbb{K}</math>, y se dice que dos valoraciones son ''equivalentes'' si generan la misma topología. Un ''primo de <math>\mathbb{K}</math>'' es una [[clase de equivalencia]] de valoraciones. Con esta definición, los primos del cuerpo <math>\mathbb{Q}</math> de los [[número racional|números racionales]] quedan representados por la función [[valor absoluto]] así como por las [[número p-ádico|valoraciones ''p''-ádicas]] sobre <math>\mathbb{Q}</math> para cada número primo ''p''.

=== Nudos primos ===
{|class="wikitable" style="margin-bottom: 1em; margin-left: 1em;" align="right"
|[[Archivo:TrefoilKnot-01.png|Trefoil|50 px]] || [[Archivo:PrimeKnot-4-1.png|Figure-8 knot]] || [[Archivo:Knot-cinquefoil-sm.png|Cinquefoil]] || [[Archivo:PrimeKnot-5-2.png]]
|-
| colspan="4" |Algunos nudos primos.
|}
En [[teoría de nudos]], un [[nudo primo]] es un [[nudo (matemáticas)|nudo]] no trivial que no se puede descomponer en dos nudos más pequeños. De forma más precisa, se trata de un nudo que no se puede escribir como [[suma conexa]] de dos nudos no triviales.

En 1949 [[Horst Schubert]] demostró un teorema de factorización análogo al teorema fundamental de la aritmética, que asegura que cada nudo se puede obtener de forma única como suma conexa de nudos primos.<ref>[http://mathworld.wolfram.com/PrimeKnot.html En Mathworld]. (en inglés)</ref> Por este motivo, los nudos primos desempeñan un papel central en la teoría de nudos: una clasificación de los nudos ha sido desde finales del siglo {{versalita|xix}} el tema central de la teoría.

== Aplicaciones en la matemática ==
* En el estudio de los números complejos, se acude al concepto de "primos relativos" para definir ''raíces primitivas de la unidad'' .<ref>Kurosch. «Álgebra superior»</ref> Si n es un número primo todas las raíces enésimas de 1 son raíces primitivas, salvo la raíz 1.

* En la definición de un ''[[cuerpo finito]]'', se exige que el número de elementos de un anillo sea entero primo. En tal caso, eliminando el cero, cada elemento tiene inverso multiplicativo y se obtiene la estructura de un cuerpo.<ref>Fraleig. «Álgebra abstracta»</ref>

* En la definición de un polígono estrellado de ''n'' lados, para tomar los puntos de ''m'' en ''m'', se exige que ''m'' sea menor que ''n/2'' y primo con ''n''.<ref>G.M.Bruño. «Elementos de geometría»</ref>

* Al definir el ''representante canónico'' de un número racional, usando clases de equivalencia de pares ordenados de números enteros, necesariamente, el par ordenado definente tiene que involucrar dos enteros primos relativos. A fortiori, por lo menos uno de ellos, un primo absoluto.<ref>C. A. Trejo «El concepto de número»</ref>

== Aplicaciones en la computación ==
{{AP|Algoritmo RSA}}
El [[RSA|algoritmo RSA]] se basa en la obtención de la [[Criptografía de clave pública|clave pública]] mediante la multiplicación de dos números grandes (mayores que 10<sup>100</sup>) que sean primos. La seguridad de este [[algoritmo]] radica en que no se conocen maneras rápidas de factorizar un número grande en sus factores primos utilizando [[Computadora electrónica|computadoras tradicionales]].

== Números primos en el arte y la literatura ==
* Los números primos han influido en numerosos artistas y escritores. El compositor francés [[Olivier Messiaen]] se valió de ellos para crear música no métrica. En obras tales como ''La Nativité du Seigneur'' (1935) o ''[[Quatre Études de rythme]]'' (1949-50) emplea simultáneamente motivos cuya duración es un número primo para crear ritmos impredecibles. Según Messiaen, esta forma de componer fue «inspirada por los movimientos de la naturaleza, movimientos de duraciones libres y desiguales».<ref>{{Cita libro |título=The Messiaen companion |autor=Peter Hill |editor=Amadeus Press |año=1994|ISBN=ISBN 0-931340-95-0}}.</ref>

* En la novela escrita en 1968 ''[[2001: A Space Odyssey (novela)|2001: Una Odisea Espacial]]'', [[Arthur C. Clarke]] menciona que el monolito de origen extraterrestre tiene la proporción del cuadrado de los primeros tres números primos: 1,4,9.

* En su novela de ciencia ficción ''[[Contact (novela)|Contact]]'', posteriormente [[Contact (película)|adaptada al cine]], [[Carl Sagan]] sugiere que los números primos podrían ser empleados para comunicarse con inteligencias extraterrestres, una idea que había desarrollado de manera informal con el astrónomo estadounidense [[Frank Drake]] en 1975.<ref>[[Carl Pomerance]], [http://www.math.dartmouth.edu/~carlp/PDF/extraterrestrial.pdf Prime Numbers and the Search for Extraterrestrial Intelligence], accedido el 31-05-2009</ref>

* ''[[El curioso incidente del perro a medianoche]]'', de Mark Haddon, que describe en primera persona la vida de un joven [[autismo|autista]] muy dotado en matemáticas y [[cálculo mental]], utiliza únicamente los números primos para numerar los capítulos.

* En la novela ''[[PopCo]]'' de [[Scarlett Thomas]], la abuela de Alice Butler trabaja en la demostración de la [[hipótesis de Riemann]]. El libro ilustra una tabla de los mil primeros números primos.<ref>[http://math.cofc.edu/kasman/MATHFICT/mfview.php?callnumber=mf476 A Mathematician reviews PopCo] {{Wayback|url=http://math.cofc.edu/kasman/MATHFICT/mfview.php?callnumber=mf476 |date=20081212025520 }} (en inglés), accedido el 31-05-2009</ref>

*''[[La soledad de los números primos]]'', novela escrita por [[Paolo Giordano]], ganó el [[premio Strega]] en 2008.

* También son muchas las películas que reflejan la fascinación popular hacia los misterios de los números primos y la criptografía, por ejemplo, ''[[Cube]]'', ''[[Sneakers (película de 1992)|Sneakers]]'', ''[[El amor tiene dos caras]]'' y ''[[A Beautiful Mind|Una mente maravillosa]]''. Esta última se basa en la biografía del matemático y premio Nobel [[John Forbes Nash]], escrita por [[Sylvia Nasar]].<ref>[http://www.musicoftheprimes.com/films.htm Music of the Spheres] {{Wayback|url=http://www.musicoftheprimes.com/films.htm |date=20151009135943 }}, Selección de [[Marcus du Sautoy]] de películas que versan sobre los números primos (en inglés), accedido el 31-05-2009</ref>

* El escritor griego [[Apostolos Doxiadis]], escribió ''[[El tío Petros y la conjetura de Goldbach]]'', que narra cómo un ficticio matemático prodigio de principios del siglo {{versalita|xx}} se sumerge en el mundo de las matemáticas de una forma apasionante, tratando de resolver uno de los problemas más difíciles y aún no resueltos de la matemática, la conjetura de Goldbach, la cual reza: «Todo número par puede expresarse como la suma de dos números primos».

== Véase también ==
{{lista de columnas|3|
* [[Criptografía]]
* [[Diferencia entre dos números primos consecutivos]]
* [[Dominio de factorización única|Anillo factorial]]
* [[Elemento irreducible]]
* [[Elemento primo]]
* [[Entero gaussiano]]
* [[Espiral de Ulam]]
* [[Fórmula de los números primos]]
* [[Mayor número primo conocido]]
* [[Número primo de grado industrial]]
* [[Número primo ilegal]]
* [[Primo de Solinas]]
* [[Probable primo]]
* [[Test de primalidad]]
* [[Anexo:Números primos]]
* [[Anexo:Tabla de factores primos]]
}}
{{portal|Matemática}}
{{Clasificación números}}

== Referencias ==
{{listaref|2}}

== Enlaces externos ==
{{wikilibros
| nombre = Implementación de algoritmos de teoría de números/Números primos
| etiqueta = cálculo de números primos 
| objeto = un libro o manual sobre
| preposición = 
| idioma = 
}}
* {{Cita publicación
 |url=http://www.brainum.es/code/ccplusplus/sacando-nmeros-primos-por-la-criba-de-eratstenes-en-c
 |título=Criba de Eratóstenes para buscar los números primos aplicada en C/C++
 |publicación=Brainum Code
}}
* [http://www.mathstools.com/section/main/calculador_factores_primos Calculador en línea de factores primos, por www.mathstools.com]
* [http://www.utm.edu/research/primes The Prime Pages] {{Wayback|url=http://www.utm.edu/research/primes |date=20040607160942 }}
* Sobre el artículo de Manindra Agrawal et al. PRIMES IS IN P, en donde afirman: "We present a deterministic polynomial-time algorithm that determines whether an input number ''n'' is prime or composite" [https://web.archive.org/web/20030814173921/http://members.cox.net/mathmistakes/primes.htm mathmistakes]
* [http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm Algoritmos eficientes para calcular números primos, por Steve Litt]
* [http://www.mste.uiuc.edu/html.f/resource/prime.html ¿Es este número primo?]

{{Conjeturas sobre números primos}}
{{Control de autoridades}}
[[Categoría:Números primos| ]]
[[Categoría:Aritmética]]