Verificatore di numeri primi

I numeri primi hanno esattamente due divisori: 1 e se stessi.

I primi numeri primi sono 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

I numeri primi sono i mattoni di tutti i numeri interi.

Ogni numero intero > 1 può essere espresso in modo unico come prodotto di numeri primi.

Ad esempio, 60 = 2² × 3 × 5.

Questo è fondamentale in matematica e crittografia.

Per verificare se un numero n è primo, controlla se un qualsiasi intero compreso tra 2 e la radice quadrata di n lo divide esattamente; se nessuno lo fa, n è primo.

Prima gestisci i casi piccoli:

• i numeri inferiori a 2 non sono primi
• 2 e 3 sono primi
• qualsiasi numero pari superiore a 2 è composto

Quindi testa i divisori dispari fino a √n, poiché i divisori si presentano sempre in coppie il cui membro più piccolo non può superare la radice quadrata.

Ad esempio, per controllare 97 è sufficiente testare 3, 5 e 7 (poiché √97 ≈ 9.85), e nessuno lo divide, quindi 97 è primo. Wolfram MathWorld descrive questo processo come divisione per tentativi, il test di primalità più diretto.

Il metodo della radice quadrata significa che devi testare solo i potenziali divisori fino a √n anziché arrivare fino a n.

Il motivo è che se n = a × b, allora almeno uno dei fattori a o b deve essere minore o uguale a √n; altrimenti il loro prodotto supererebbe n. Quindi, se non si trova alcun fattore sotto √n, non esiste nemmeno alcun fattore più grande.

Questo riduce drasticamente il lavoro: verificare se 9.973 è primo richiede di testare i divisori solo fino a circa 99, e non quasi 10.000.

Khan Academy usa questo argomento delle coppie per spiegare perché la divisione per tentativi si ferma alla radice quadrata, rendendo praticico il controllo manuale della primalità.

Il Crivello di Eratostene trova tutti i numeri primi fino a un limite N contrassegnando ripetutamente i multipli di ciascun numero primo come composti.

Inizia con un elenco di interi da 2 a N. Prendi il 2, contrassegna 4, 6, 8, ... come composti; passa al numero successivo non contrassegnato, il 3, e contrassegna 6, 9, 12, ...; continua con 5, 7 e così via. I numeri che rimangono non contrassegnati sono primi.

Applicato fino a 30, il crivello lascia 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Prende il nome dal matematico greco Eratostene di Cirene, questo algoritmo (documentato da Encyclopaedia Britannica) è uno dei modi più antichi ed efficienti per elencare i numeri primi in un intervallo.

Il Teorema Fondamentale dell'Aritmetica afferma che ogni intero maggiore di 1 è primo o può essere scritto come prodotto di numeri primi in un modo esattamente unico, a parte l'ordine dei fattori.

Ad esempio, 360 = 2³ × 3² × 5, e nessun'altra combinazione di numeri primi dà 360 se moltiplicata. Questa unicità è il motivo per cui i numeri primi sono chiamati i mattoni degli interi.

Secondo Wolfram MathWorld, questo teorema è alla base della fattorizzazione prima, del calcolo del massimo comun divisore e dell'aritmetica modulare.

La nostra calcolatrice matematica lo utilizza quando fattorizza un numero, garantendo che la scomposizione in fattori primi restituita sia l'unica possibile.

I numeri primi gemelli sono coppie di numeri primi che differiscono esattamente di 2, come (3, 5), (5, 7), (11, 13), (17, 19) e (29, 31).

La distanza tra numeri primi consecutivi generalmente cresce man mano che i numeri diventano più grandi, sebbene i numeri primi gemelli continuino ad apparire. Se esistano o meno infiniti numeri primi gemelli è la famosa congettura dei numeri primi gemelli, ancora non dimostrata.

The On-Line Encyclopedia of Integer Sequences (OEIS) cataloga i membri inferiori delle coppie di primi gemelli nella sequenza A001359.

Comprendere la distanza tra i numeri primi aiuta a spiegare perché i numeri primi diventano più radi: vicino a un milione, i numeri primi sono distanziati in media di circa 14, una tendenza descritta dal Teorema dei Numeri Primi nella Digital Library of Mathematical Functions del NIST.

I numeri primi alimentano la crittografia moderna, in particolare la cifratura RSA, che protegge l'internet banking, i siti web HTTPS e le firme digitali. RSA si basa sul fatto che moltiplicare due grandi numeri primi è facile, ma fattorizzare il prodotto ottenuto per tornare a quei numeri primi è computazionalmente difficile.

Oltre alla sicurezza, i numeri primi compaiono in:

• dimensionamento delle tabelle hash (le tabelle con lunghezza prima riducono le collisioni)
• generazione di numeri pseudo-casuali
• codici di correzione degli errori
• cicli di vita delle cicale che si sono evoluti attorno ad anni con numeri primi per evitare i predatori

La Britannica nota che la fattorizzazione prima semplifica anche le frazioni e calcola i minimi comuni multipli. Questa calcolatrice online supporta queste attività fattorizzando i numeri e generando numeri primi sia per la progettazione di algoritmi che per i compiti di matematica.

Un numero primo ha esattamente due divisori positivi distinti, 1 e se stesso, mentre un numero composto ha più di due divisori.

Ad esempio, 13 è primo (divisori 1 e 13) e 12 è composto (divisori 1, 2, 3, 4, 6, 12). Il numero 1 non è né primo né composto, perché ha un solo divisore.

Questa convenzione mantiene pulito il Teorema Fondamentale dell'Aritmetica: se l'1 fosse contato come primo, le fattorizzazioni non sarebbero più uniche poiché si potrebbe inserire un qualsiasi numero di 1.

Sia l'Encyclopaedia Britannica che Khan Academy sottolineano questa distinzione, ed è per questo che il nostro strumento classifica l'1 separatamente dai numeri primi e composti.

I numeri primi di Mersenne sono numeri primi della forma 2^p − 1, dove l'esponente p è a sua volta primo; gli esempi includono 3 (2² − 1), 7 (2³ − 1), 31 (2⁵ − 1) e 127 (2⁷ − 1).

Tuttavia, non ogni esponente primo produce un numero primo: 2¹¹ − 1 = 2047 = 23 × 89 è composto.

I numeri primi di Mersenne sono importanti perché un test veloce chiamato test di Lucas-Lehmer li rende più facili da verificare rispetto a numeri arbitrari, quindi i numeri primi più grandi conosciuti sono quasi sempre numeri primi di Mersenne con decine di milioni di cifre.

The Great Internet Mersenne Prime Search (GIMPS) coordina i volontari per scoprirli. La sequenza OEIS A000668 elenca i numeri primi di Mersenne conosciuti.

• L'errore più comune è trattare l'1 come un numero primo; non lo è, perché un numero primo deve avere esattamente due divisori.
• Un altro errore è dimenticare che il 2 è l'unico numero primo pari, quindi le persone lo saltano erroneamente o presumono erroneamente che altri numeri pari possano essere primi.
• Un terzo errore è interrompere la divisione per tentativi troppo presto o troppo tardi: devi testare tutti i divisori fino a √n, non solo alcuni piccoli.
• Le persone confondono anche la fattorizzazione prima con l'elenco di tutti i fattori; 12 ha come fattori 1, 2, 3, 4, 6, 12 ma una fattorizzazione prima di soli 2² × 3.
• Infine, dare per scontato che ogni numero della forma 6k ± 1 sia primo è falso; 25 = 6(4) + 1 è composto.