primalità

Primalità è una proprietà dei numeri naturali. Un numero maggiore di 1 è primo se ha esattamente due divisori positivi: 1 e se stesso. Se è possibile dividerlo anche per altri numeri interi, allora non è primo ed è detto composto. 1 non è né primo né composto.

I numeri primi sono i mattoni fondamentali degli interi: ogni intero maggiore di 1 può essere espresso in modo univoco come prodotto di primi, se si tiene conto dell’ordine solo delle moltiplicazioni. Questo è enunciato dal teorema fondamentale dell'aritmetica.

Per determinare la primalità di un numero si possono usare vari metodi. La verifica per divisione richiede controllare i divisori fino alla radice quadrata del numero. La sieve di Eratostene consente di elencare tutti i primi fino a N. Esistono test di primalità probabilistici come Miller-Rabin e versioni deterministiche valide per intervalli specifici.

2 è l’unico numero primo pari; tutti gli altri numeri pari sono compositi. 1 non è né primo né composto. I primi hanno applicazioni in vari campi, tra cui la crittografia (ad es. RSA) e la teoria dei numeri. La distribuzione dei primi è studiata nel contesto del teorema dei numeri primi, secondo cui il numero di primi minore o uguale a x è circa x/log x.