numbers Lista e Verifica dei Numeri Primi star

Come Funziona

Lo strumento passa tra due algoritmi diversi, ciascuno adatto a una domanda differente. La modalità elenco trova ogni numero primo fino a un limite usando il Crivello di Eratostene, uno degli algoritmi più antichi ancora in uso quotidiano (attribuito al matematico greco Eratostene, III secolo a.C.). Partendo da 2, segna come composto ogni multiplo di 2, poi passa al numero non segnato successivo (3) e ne segna tutti i multipli, poi al numero non segnato successivo (5), e così via. Tutto ciò che sopravvive non segnato una volta raggiunta la radice quadrata del limite è primo. Un piccolo esempio: per crivellare fino a 30, elimina i multipli di 2 (4, 6, 8, …), poi i multipli di 3 (6, 9, 12, …, alcuni già eliminati), poi i multipli di 5 (10, 15, …) — poiché 5×5=25 ≤ 30 ma 7×7=49 > 30, puoi fermarti qui; ciò che rimane — 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — è l'elenco completo. Questo procedimento gira in tempo O(n log log n), il che significa che resta veloce anche quando l'intervallo cresce fino alle centinaia di migliaia.

La modalità verifica risponde a una domanda diversa — questo specifico numero è primo? — usando la divisione di prova fino alla radice quadrata. Per verificare se n è primo, basta controllare i divisori da 2 fino a √n. Il ragionamento: se n = a × b con sia a sia b maggiori di √n, allora a × b sarebbe maggiore di n, il che è impossibile. Quindi almeno uno dei due fattori deve essere √n o inferiore, e verrà trovato prima che il ciclo finisca. Esempio: per verificare 97, basta testare la divisibilità per 2, 3, 5, 7 (poiché 9²=81 ≤ 97 ma 10²=100 > 97) — nessuno divide esattamente, quindi 97 è primo.

Cosa Sapere

Le due modalità esistono perché comportano compromessi diversi: il crivello è efficiente per produrre molti numeri primi in una volta, ma spreca memoria e tempo se ti interessa un solo numero vicino a un limite enorme; la divisione di prova è efficiente per una singola verifica, ma è di gran lunga troppo lenta se ripetuta per ogni numero di un ampio intervallo uno alla volta. Scegliere quella giusta per il compito è esattamente il motivo per cui questo strumento offre entrambe.

• L'1 è escluso dai numeri primi per definizione e convenzione — ha un solo divisore, non due, il che comprometterebbe l'unicità della scomposizione in fattori primi se fosse ammesso.
• Il 2 è l'unico numero primo pari; ogni altro numero pari è divisibile per 2 e quindi composto.
• Al crescere dei numeri, i numeri primi diventano mediamente più rari, ma non smettono mai di comparire — Euclide dimostrò oltre duemila anni fa che ne esistono infiniti.