Uno degli argomenti centrali della teoria dei numeri sono i numeri primi. I numeri primi sono un insieme speciale di numeri naturali maggiori di $1$ che sono divisibili solo per $1$ e per se stessi. L'importanza dei numeri primi risiede in vari campi come la crittografia, l'informatica e la fisica. La generazione di numeri primi può essere un compito impegnativo, soprattutto per i numeri grandi. Lo studio dei numeri primi ha molte applicazioni in campi come la crittografia, la teoria della codifica e l'informatica. Ad esempio, la sicurezza di molti schemi di crittografia si basa sul fatto che la fattorizzazione di grandi numeri composti in numeri primi è un problema difficile. La complessità computazionale per il calcolo dei numeri primi incrementa con l’ordine di grandezza del numero $n$. All'aumentare del valore di $n$, aumenta il numero di iterazioni necessarie per verificare se un numero è primo, che porta a tempi di esecuzione più lunghi (un normale algoritmo ha complessità $\sim O\left(\sqrt{n}\right)$). Un modo efficace per verificare se un numero sia primo è quello di verificare la sua divisibilità fino alla radice quadrata di $n$, perché ogni fattore di un numero deve essere minore o uguale alla sua radice quadrata. Se un numero $N$ non è primo, allora esiste almeno un fattore, chiamiamolo $F$, diverso da $1$ e da $N$ stesso, tale che $N = F \cdot Q$. Se $F > \sqrt{N}$, allora $Q < \sqrt{N}$, altrimenti si avrebbe $F \cdot Q > N$. Pertanto, quando controlliamo tutti i numeri da $2$ fino a $int\left(\sqrt{n}\right) + 1$, se non abbiamo trovato alcun fattore di $n$ fino a quel punto, allora $n$ non può essere divisibile per nessun numero maggiore della sua radice quadrata. La distribuzione dei numeri primi è un problema fondamentale della teoria dei numeri, con molte importanti questioni aperte. Il teorema dei numeri primi, dimostrato da Jacques Hadamard e Charles de la Vallée-Poussin indipendentemente nel 1896, fornisce una stima del numero di numeri primi inferiori a un dato numero $x$. Il teorema afferma che il numero di numeri primi inferiori a $x$ è approssimativamente uguale a $\frac{x}{log(x)}$. Ciò significa che, al crescere di $x$, il rapporto tra i primi e tutti i numeri inferiori a $x$ si avvicina a zero. Esistono molti altri risultati e congetture importanti nella teoria dei numeri primi, come:
Il codice fornisce due funzioni per generare e verificare i numeri primi:
Il codice utilizza un approccio semplice per generare i numeri primi, iterando tutti i numeri a partire da $2$ e verificando se sono primi utilizzando la funzione is_prime(). I numeri primi vengono aggiunti all'elenco dei primi finché l'elenco non contiene il numero di primi richiesto. La funzione main() genera, per defualt, i primi $10000$ numeri primi e calcola il tempo impiegato per farlo. L'elenco dei primi e il tempo di esecuzione vengono stampati nella console. Si noti che il tempo impiegato per generare i numeri primi può essere significativo, soprattutto per i numeri grandi. Il programma può essere esteso e modificato per scopi diversi, come la modellazione di processi naturali o la generazione di dati casuali a scopo di test.