Comprovador de nombres primers

Com utilitzar el comprovador de nombres primers

1. Escriu un Nombre enter. També s’accepten expressions: 2^61-1, 10^12+39, 20!+1 o 3711.
2. La resposta apareix mentre escrius; prem Comprova per donar més temps a la factorització d’un nombre difícil.
3. Llegeix el veredicte, la Descomposició en factors primers, el Nombre de divisors, el Primer anterior i el Primer següent. El quadre Per què explica com s’ha arribat a la resposta, i Copia la factorització copia el producte de primers.
4. Per llistar primers, omple els camps De i A de Nombres primers en un interval i prem Llista els primers.

S’accepten nombres de fins a 2048 bits (unes 617 xifres), i tot s’executa al teu navegador: res del que escrius s’envia a cap servidor.

Què fa que un nombre sigui primer

Un nombre primer és un nombre enter més gran que 1 els únics divisors del qual són 1 i ell mateix: 2, 3, 5, 7, 11, 13… Un nombre que té altres divisors és compost, i es pot escriure d’una sola manera com a producte de primers, la seva descomposició en factors primers (360 = 2³ × 3² × 5). Els nombres 0 i 1 no són ni primers ni compostos, i 2 és l’únic primer parell.

El nombre de divisors es dedueix de la descomposició: suma 1 a cada exponent i multiplica. 360 = 2³ × 3² × 5 té (3 + 1)(2 + 1)(1 + 1) = 24 divisors. Un primer en té sempre exactament 2.

Com funciona el test

• Els nombres petits (per sota d’un milió) es comproven per divisió d’assaig: si cap primer fins a l’arrel quadrada divideix el nombre, és primer. No cal anar més enllà, perquè un nombre compost sempre té un factor que no supera la seva arrel quadrada.
• Els nombres més grans es divideixen primer per tots els primers inferiors a 1000 i després passen pel test de Miller–Rabin. Amb les 13 bases 2, 3, 5, …, 41, aquest test està demostrat com a exacte per a tots els nombres inferiors a 3,3 × 10²⁴, cosa que inclou tots els enters de 64 bits. Per a aquests nombres, la resposta és certa.
• Per sobre de 3,3 × 10²⁴ s’utilitzen 25 bases, i un nombre que les supera totes s’indica com a primer probable. La probabilitat d’error és inferior a 1 entre 10¹⁵, però no és una demostració matemàtica. Quan el test falla, el nombre és compost sense cap dubte.

Com es factoritzen els nombres

Els factors petits es troben per divisió d’assaig. Les parts compostes més grans es parteixen amb l’algorisme rho de Pollard (variant de Brent), que troba factors de fins a unes 10 xifres en una fracció de segon. Els nombres més difícils, com el producte de dos primers de 15 xifres o més, poden trigar molt més que qualsevol límit de temps, de manera que la factorització s’atura al cap d’uns quants segons. L’últim factor es marca aleshores com a compost però sense descompondre, i si tornes a prémer Comprova, li dones més temps.

Primers en un interval

La llista d’intervals utilitza un garbell d’Eratòstenes segmentat, que ratlla els múltiples de cada primer. Accepta fins a 1 000 000 de nombres per interval, amb un límit superior de fins a 10¹². El recompte cobreix tot l’interval i es llisten els 2000 primers nombres primers. Per exemple, hi ha 25 primers entre 1 i 100, i 78 498 per sota d’un milió.