0002 0003 0005 0007 0011 0013 0017 0019 0023 0029 0031 0037 0041 0043 0047 0053 0059 0061 0067 0071 
0073 0079 0083 0089 0097 0101 0103 0107 0109 0113 0127 0131 0137 0139 0149 0151 0157 0163 0167 0173 
0179 0181 0191 0193 0197 0199 0211 0223 0227 0229 0233 0239 0241 0251 0257 0263 0269 0271 0277 0281 
0283 0293 0307 0311 0313 0317 0331 0337 0347 0349 0353 0359 0367 0373 0379 0383 0389 0397 0401 0409 
0419 0421 0431 0433 0439 0443 0449 0457 0461 0463 0467 0479 0487 0491 0499 0503 0509 0521 0523 0541 
0547 0557 0563 0569 0571 0577 0587 0593 0599 0601 0607 0613 0617 0619 0631 0641 0643 0647 0653 0659 
0661 0673 0677 0683 0691 0701 0709 0719 0727 0733 0739 0743 0751 0757 0761 0769 0773 0787 0797 0809 
0811 0821 0823 0827 0829 0839 0853 0857 0859 0863 0877 0881 0883 0887 0907 0911 0919 0929 0937 0941 
0947 0953 0967 0971 0977 0983 0991 0997 

In matematica l'aggettivo primo è usato in due accezioni leggermente diverse:

• numero primo [assoluto]: è un numero naturale (intero positivo) $N$ che ha 2 e 2 soli divisori che sono ovviamente 1 ed N stesso; p.es. 2, 3, 5, 7, 11, 13 ...; il numero 1 viene quindi di norma escluso avendo un solo divisore (se stesso).
• numeri primi tra di loro: due numeri $M$ e $N$ si dicono primi tra di loro se hanno come unico divisore comune 1; detto in altri termini deve essere $MCD(M, N) = 1$. P.es. $25$ in assoluto non è primo, 9 in assoluto non è primo ma 25 e 9 sono primi tra di loro avendo $MCD(25, 9) = 1$.

Nella tabella a destra sono elencati i numeri primi minori di 1000.

La teoria dei numeri primi nasce intorno al 300AC ad Alessandria con Euclide che negli Elementi riporta alcuni risultati fondamentali:

• Esistono infiniti numeri primi.
• Ogni numero non primo può scomporsi nel prodotto di più numeri primi e questa scomposizione è unica.

Pochi anni dopo, sempre ad Alessandria, Eratostene definisce un metodo per trovare la lista di tutti i numeri primi minori di un dato numero N. Questo metodo, noto come il crivello di Eratostene, è tuttora il più efficiente metodo per generare liste di primi.

Da allora non è che si siano fatti molti progressi nella conoscenza dei numeri primi; i risultati più importanti furono ottenuti da Eulero, circa 2000 anni dopo Euclide, con la dimostrazione del teorema di Eulero-Fermat e l'introduzione della funzione di Eulero.

Eulero diede inoltre una nuova e sorprendente dimostrazione dell'infinità dei numeri primi, dimostrazione che un secolo dopo portò Riemann a formulare quella congettura di Riemann che attende ancora oggi una dimostrazione (o una confutazione).

Negli ultimi anni la disponibilità di computer con elevate capacità di calcolo ha permesso di scoprire numeri primi sempre più grandi, ma non ha fatto fare passi avanti alla teoria!

In definitiva sappiamo ancora molto poco sui numeri primi. In particolare:

• Tra quel poco che sappiamo è importante la formula, trovata da Gauss e Legendre, che approssima per difetto il numero di numeri primi minori di un dato $x$; la funzione che calcola questo numero è indicata di solito con $\pi(x)$ e la formula di Gauss e Legendre è: $$ \pi(x) \approx \frac{x}{\ln(x)} $$ Una variante più accurata è data da $ \frac{x}{\ln(x)-1} $, e una ancora migliore dalla funzione $ \text{li}(x) = \int_0^x{\frac{1}{\ln(t)}}{dt}$. Sotto la lista di numeri prima a destra vengono confrontati il numero contato di numeri primi con i valori previsti dalle prime due formule.
• Non si conosce una formula che permetta di generare i numeri primi, p.es. una funzione che ci permetta di calcolare il 1000º numero primo.
• La distribuzione dei numeri primi sembra a prima vista casuale; non sappiamo ancora se sia effettivamente così o se vi sia una qualche regolarità rimasta fino ad ora nascosta.
• Sono frequenti i numeri primi gemelli cioè accoppiati a distanza di 2; le prime coppie sono (5, 7) (11, 13), (17, 19), (29, 31); non sappiamo se la serie dei primi gemelli sia finita o infinita.
• Non si conoscono metodi veloci per stabilire se un numero è primo (test di primalità).
• Non si conoscono metodi veloci per scomporre un numero in fattori primi.

Il fatto di sapere così poco sui numeri primi si è rivelato un vantaggio per i crittologi; oggi quasi tutti i computer usano per comunicare in modo riservato il cifrario RSA basato appunto sulla difficoltà di scomporre in fattori primi numeri molto grandi (centinaia di cifre decimali).

Se un giorno un matematico dovesse scoprire un metodo per trovare velocemente i fattori primi di un qualsiasi numero, il cifrario RSA perderebbe di colpo tutta la sua sicurezza!

Alcuni ritengono che una chiave del problema sia la congettura di Riemann; se venisse dimostrata potrebbe aprirsi la strada ad algoritmi veloci per la fattorizzazione di un numero qualsiasi. Ma siamo appunto nel campo delle congetture.