Scomposizione in fattori primi e numeri primi

Scomporre un numero e capire se è primo

Questo strumento risponde a due domande frequenti in matematica: un numero è primo? E qual è la sua scomposizione in fattori primi? Scrivi un intero fino a 40 cifre e ottieni la risposta, il metodo usato, la scomposizione con le potenze (per esempio 2³ × 3² × 5), il numero di divisori, il loro elenco e i numeri primi precedente e successivo. Un secondo modo fornisce l'elenco dei numeri primi fino a 10 milioni.

Come si usa

1. Scegli «Verifica e scomponi un numero», scrivilo in «Numero intero» e premi «Analizza» o Invio. Accetta anche le potenze: 2^61 − 1.
2. Leggi la «Scomposizione in fattori primi», il «Numero di divisori», il «Primo precedente» e il «Primo successivo». Le «Divisioni successive» mostrano il procedimento.
3. Spunta «Mostra l'albero dei fattori» per vedere l'albero e «Mostra l'elenco dei divisori» per tutti i divisori con la loro somma.
4. Per un elenco scegli «Elenco dei numeri primi», scrivi N in «Numeri primi fino a N» e premi «Mostra l'elenco». «Scarica l'elenco (.txt)» salva l'elenco completo.

Che cosa sono i numeri primi

Un numero primo è un intero che ha esattamente due divisori: 1 e sé stesso. Sono primi 2, 3, 5, 7, 11 e 13; il 2 è l'unico primo pari. L'1 non è primo, perché ha un solo divisore, e nemmeno lo 0. Gli interi maggiori di 1 che non sono primi si chiamano composti.

Per capire se un numero è primo basta dividerlo per gli interi da 2 fino alla sua radice quadrata. Per 97, √97 ≈ 9,8: né 2, né 3, né 5, né 7 lo dividono, quindi è primo. Attenzione a 87: sembra primo, ma 87 = 3 × 29. Con numeri molto grandi lo strumento usa il test di Miller-Rabin, che dà una risposta dimostrata per ogni numero fino a 2⁶⁴ e oltre.

Come si scompone un numero

Si divide per il più piccolo numero primo possibile finché la divisione è esatta, poi si passa al successivo. Con 1980: 1980 ÷ 2 = 990, 990 ÷ 2 = 495, 495 ÷ 3 = 165, 165 ÷ 3 = 55, 55 ÷ 5 = 11, 11 ÷ 11 = 1. Quindi 1980 = 2² × 3² × 5 × 11. La scomposizione è unica, a parte l'ordine dei fattori. Dà anche il numero di divisori: si aggiunge 1 a ogni esponente e si moltiplica, 3 × 3 × 2 × 2 = 36 divisori. I primi vicini sono 1979 e 1987.

La scomposizione serve a semplificare le frazioni e a calcolare MCD e mcm.

Il crivello di Eratostene

Per trovare i primi fino a N si scrivono i numeri da 2 a N, si tiene il 2 e si cancellano i suoi multipli, poi si tiene il primo numero non cancellato, il 3, e si cancellano i suoi multipli, e così via. Fino a 100 basta cancellare i multipli di 2, 3, 5 e 7: restano 25 numeri primi. Fino a 10 milioni sono 664.579 e lo strumento li calcola in meno di un secondo.

I numeri primi sono infiniti, come dimostrò Euclide più di 2000 anni fa. Alcuni sistemi di crittografia si basano sul fatto che, con i metodi conosciuti, ritrovare due grandi numeri primi dal loro prodotto richiede un'enorme quantità di calcoli quando hanno centinaia di cifre.

Domande frequenti

Perché 1 non è un numero primo?

Un primo deve avere esattamente due divisori distinti e l'1 ne ha uno solo. Escluderlo mantiene anche unica la scomposizione: altrimenti 6 si potrebbe scrivere 2 × 3, 1 × 2 × 3, 1 × 1 × 2 × 3…

Fino a che dimensione funziona?

Fino a 40 cifre. Il test di primalità è quasi immediato. La scomposizione del prodotto di due grandi primi può richiedere tempo: dopo 10 secondi il calcolo si ferma e indica il fattore che non è riuscito a scomporre.

2⁶¹ − 1 è un numero primo?

Sì: 2⁶¹ − 1 = 2.305.843.009.213.693.951 è un primo di Mersenne. Scrivi 2^61 − 1 per verificarlo. Il più grande primo minore di 2⁶⁴ è 18.446.744.073.709.551.557.