Verifica numeri primi

Come usare la verifica dei numeri primi

1. Scrivi un Numero intero. Sono accettate anche le espressioni: 2^61-1, 10^12+39, 20!+1 o 3711.
2. La risposta compare mentre scrivi; premi Verifica per dare più tempo alla scomposizione quando il numero è difficile.
3. Leggi il verdetto, la Scomposizione in fattori primi, il Numero di divisori, il Primo precedente e il Primo successivo. Il riquadro Perché spiega come si è arrivati alla risposta, e Copia la scomposizione copia il prodotto dei fattori primi.
4. Per elencare i numeri primi compila Da e A in Numeri primi in un intervallo e premi Elenca i primi.

Sono accettati numeri fino a 2048 bit (circa 617 cifre), e tutto il calcolo avviene nel tuo browser.

Quando un numero è primo

Un numero primo è un intero maggiore di 1 che ha come unici divisori 1 e se stesso: 2, 3, 5, 7, 11, 13… Un numero con altri divisori è composto e si può scrivere in un solo modo come prodotto di numeri primi, la sua scomposizione in fattori primi (360 = 2³ × 3² × 5). I numeri 0 e 1 non sono né primi né composti, e 2 è l’unico numero primo pari.

Il numero di divisori si ricava dalla scomposizione: aggiungi 1 a ogni esponente e moltiplica. 360 = 2³ × 3² × 5 ha (3 + 1)(2 + 1)(1 + 1) = 24 divisori. Un numero primo ne ha sempre esattamente 2.

Come funziona il test

• I numeri piccoli (sotto il milione) si verificano per divisioni successive: se nessun primo fino alla radice quadrata divide il numero, il numero è primo. Non serve andare oltre, perché un numero composto ha sempre un fattore non più grande della sua radice quadrata.
• I numeri più grandi vengono prima divisi per tutti i primi minori di 1000, poi sottoposti al test di Miller–Rabin. Con le 13 basi 2, 3, 5, …, 41 questo test è dimostrato esatto per ogni numero minore di 3,3 × 10²⁴, che comprende tutti gli interi a 64 bit. Per questi numeri la risposta è certa.
• Sopra 3,3 × 10²⁴ si usano 25 basi, e un numero che le supera tutte viene indicato come probabile primo. La probabilità di errore è inferiore a 1 su 10¹⁵, ma non è una dimostrazione matematica. Quando il test fallisce, il numero è sicuramente composto.

Come vengono scomposti i numeri

I fattori piccoli si trovano per divisioni successive. Le parti composte più grandi si scompongono con l’algoritmo rho di Pollard (nella variante di Brent), che trova fattori fino a circa 10 cifre in una frazione di secondo. I numeri più difficili, come il prodotto di due primi di 15 cifre o più, possono richiedere molto più tempo di qualsiasi limite, quindi la scomposizione si ferma dopo qualche secondo. L’ultimo fattore viene allora segnato come composto ma non scomposto, e premendo di nuovo Verifica gli si dà più tempo.

Numeri primi in un intervallo

L’elenco usa un crivello di Eratostene segmentato, che cancella i multipli di ogni numero primo. Accetta fino a 1.000.000 di numeri per intervallo con un limite superiore fino a 10¹². Il conteggio copre tutto l’intervallo e vengono elencati i primi 2000 numeri primi. Ad esempio, tra 1 e 100 ci sono 25 numeri primi e sotto il milione ce ne sono 78.498.