Verifica se un numero è primo, scomponilo in fattori primi, elenca tutti i primi fino a N e trova il successivo.
Un numero primo ha esattamente due divisori, 1 e se stesso. È questo che rende i primi i mattoni dell'aritmetica: ogni numero intero maggiore di 1 è un prodotto di primi in un solo modo, ed è ciò che afferma il teorema fondamentale dell'aritmetica. 360 è 2³ × 3² × 5 e nient'altro; 91 sembra primo ma in realtà è 7 × 13; 97 lo è davvero. Una volta nota la fattorizzazione, altri fatti seguono gratis — il numero di divisori è il prodotto di ciascun esponente più uno, quindi 360 ne ha (3 + 1) × (2 + 1) × (1 + 1) = 24.
Qui la verifica di primalità avviene per divisioni successive, ma solo fino alla radice quadrata del numero e solo su candidati della forma 6k ± 1, dato che tutto il resto è già multiplo di 2 o di 3. Questo taglia due terzi del lavoro e risolve un numero sotto il migliaio di miliardi in qualche centinaio di migliaia di divisioni, un paio di millisecondi. Sopra 10¹² anche questo diventa lento in un browser, quindi la risposta passa al test deterministico di Miller-Rabin con le basi da 2 a 37, dimostrato esatto per ogni numero sotto 3,3×10²⁴ e quindi per tutto ciò che questo strumento accetta, fino a 2⁵³ − 1. L'elenco dei primi usa un altro classico: il crivello di Eratostene scrive tutti i numeri fino a N, tiene il più piccolo non ancora segnato, cancella tutti i suoi multipli e ripete finché sopravvivono solo i primi.
La fattorizzazione in numeri primi è il meccanismo dietro la riduzione delle frazioni, il calcolo di mcm e MCD e la semplificazione delle radici quadrate, ed è per questo che si insegna presto. Fuori dalla scuola, la difficoltà di fattorizzare numeri grandi è ciò su cui si regge la crittografia RSA: moltiplicare due primi grandi è istantaneo, tornare indietro no, e la distanza tra le due cose è l'intero argomento di sicurezza. I primi si diradano anche in modo prevedibile man mano che i numeri crescono, pur senza finire mai — Euclide lo dimostrò più di duemila anni fa. Qui si possono verificare numeri fino a 2⁵³ − 1, la fattorizzazione e i primi vicini funzionano fino a mille miliardi, e l'elenco dei primi arriva a 100.000. Niente di ciò che digiti esce dal tuo browser.
Primalità per divisioni successive: n è primo quando nessun numero intero da 2 fino a √n lo divide, ed è sufficiente testare 2, 3 e poi ogni candidato della forma 6k ± 1. La fattorizzazione applica le stesse divisioni e registra quante volte ciascun primo ci sta; il numero di divisori è il prodotto di ciascun esponente più uno. L'elenco dei primi usa il crivello di Eratostene. Sopra 10^12 la risposta sulla primalità viene dal test deterministico di Miller-Rabin con basi da 2 a 37, esatto per ogni numero sotto 2^53.
Prova a dividerlo per ogni primo fino alla sua radice quadrata: se nessuno lo divide esattamente, il numero è primo. Per 97 la radice quadrata è sotto 10, quindi testare 2, 3, 5 e 7 basta a risolvere la questione.
No. Un primo deve avere esattamente due divisori distinti, e 1 ne ha solo uno. Escluderlo è anche ciò che rende unica la fattorizzazione in primi, perché altrimenti qualsiasi numero potrebbe essere riempito con tutti gli 1 che si vogliono.
È la base per ridurre le frazioni, calcolare MCD e mcm, semplificare le radici quadrate e contare i divisori. Scrivere 360 come 2³ × 3² × 5 dà subito i suoi 24 divisori e tutto ciò che ha in comune con un altro numero.
Fino a 9.007.199.254.740.991 — cioè 2⁵³ − 1 — per la verifica di primalità. La fattorizzazione e i primi vicini arrivano a 1.000.000.000.000 e l'elenco dei primi a 100.000, così ogni risposta resta istantanea nel browser.
Perché ogni altro numero pari è divisibile per 2, il che gli dà un terzo divisore e lo squalifica. È anche per questo che lo strumento salta i candidati pari dopo aver testato il 2.
No. Le divisioni, il crivello e il test di Miller-Rabin girano tutti in JavaScript sul tuo dispositivo, senza richieste ad alcun server e senza memorizzare nulla.
Vai.la trasforma qualsiasi URL in un link breve con statistiche dei clic, QR Code e il tuo biolink personale.
Vai.la non è responsabile dell'uso degli strumenti né delle decisioni prese in base ai loro risultati.