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:

• La congettura dei numeri primi gemelli, che afferma che esistono infinite coppie di numeri primi che differiscono per $2$.
• La congettura di Goldbach, che afferma che ogni numero intero pari maggiore di $2$ può essere espresso come somma di due numeri primi.
• L'ipotesi di Riemann, una congettura sulla distribuzione dei numeri primi che ha molte conseguenze importanti nella teoria dei numeri e non solo.

Il codice fornisce due funzioni per generare e verificare i numeri primi:

1. La funzione 'is_prime()' prende in input un numero intero $n$ e restituisce True se $n$ è un numero primo e False altrimenti. Controlla la divisibilità di $n$ fino alla radice quadrata di $n$, poiché qualsiasi fattore di un numero deve essere minore o uguale alla sua radice quadrata.
2. La funzione 'prime_numbers()' prende in input un numero intero $x$ e genera l’elenco dei primi $x$-numeri primi utilizzando la funzione is_prime().

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.