Un numero primo è un numero maggiore di 1 che è divisibile soltanto per sé stesso e per 1. Una definizione del genere suggerisce, per stabilire se il numero n è primo oppure no, di eseguire scrupolosamente la divisione euclidea di n per 2, poi per 3 e così via, finché una di esse non dia resto zero oppure non si siano provati tutti gli interi fino a n − 1. Non proprio rapido, e ancor meno facile da fare a mente… Per fortuna, un po’ di aritmetica permette di ridurre notevolmente le operazioni da svolgere, al punto che stabilire se n è primo diventa un esercizio eseguibile a mente per molti numeri non troppo grandi.
Il crivello paga ------------------
A Eratostene, direttore della biblioteca di Alessandria e corrispondente di Archimede, si attribuisce l’invenzione di un procedimento per trovare tutti i numeri primi minori di un valore N fissato in precedenza: si scrive l’elenco dei numeri interi compresi tra 2 e N, si conserva il 2 e si cancellano tutti i suoi multipli, poi si conserva il 3 e si cancellano tutti i suoi multipli, poi si conserva il 5 (dato che il 4 è stato cancellato) e si cancellano tutti i suoi multipli, e così via. Alla fine, soltanto i numeri primi compresi tra 2 e N non sono stati cancellati.
Per valutare l’efficacia del crivello di Eratostene, si può osservare che, se il prodotto di due numeri p e q è uguale a n, allora almeno uno dei due numeri p o q è minore (o uguale) di n\sqrt{n}: infatti, se entrambi fossero maggiori di n\sqrt{n}, il prodotto pq sarebbe a sua volta maggiore di n×n=n,\sqrt{n} \times \sqrt{n} = n, mentre pq = n. Ne deduciamo che, nel crivello di Eratostene, una volta cancellati i multipli degli interi n per ogni n≤Nn \le \sqrt{N} non resta più nulla da cancellare: il lavoro è finito.
Questo metodo globale di setacciamento non è certo applicabile a mente, ma può ispirarci per stabilire se un dato intero a è primo oppure no. Infatti, se a non è primo, lo si può scrivere nella forma pq e, in base all’osservazione precedente, uno di questi due fattori è al più pari a a.\sqrt{a}. Basta dunque verificare se a è divisibile per 2, 3 ecc., fino a a,\sqrt{a}, il che è comunque più rapido che arrivare fino a a − 1.