Verifica Numeri Primi e Scomposizione in Fattori

Un numero primo è un numero naturale maggiore di 1 che non ha divisori positivi diversi da 1 e da se stesso. I primi numeri primi sono 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 2 è l'unico primo pari: tutti gli altri numeri pari sono divisibili per 2 e quindi composti. Questo rende il 2 unico tra i numeri primi. Come verificare se un numero è primo: basta controllare la divisibilità per i numeri primi fino alla radice quadrata. Per testare 97: prova 2, 3, 5 e 7 (√97 ≈ 9,8). Se nessuno lo divide esattamente, è primo. I numeri primi sono infiniti: Euclide dimostrò intorno al 300 a.C. che esistono infiniti numeri primi. Il più grande primo conosciuto (al 2024) ha oltre 40 milioni di cifre. Perché i numeri primi sono importanti: la crittografia RSA (che protegge home banking, email e HTTPS) si basa sul fatto che moltiplicare due grandi numeri primi è facile, mentre risalire ai fattori primi partendo dal risultato è computazionalmente impraticabile.