Numeri primi
Controlla in un attimo se un numero è primo (e scopri il suo divisore più piccolo se non lo è), oppure genera l'elenco completo dei numeri primi fino a 100.000.
Come si verifica se un numero è primo
Un numero è primo se ha esattamente due divisori: 1 e sé stesso. Per verificarlo non serve provare tutti i numeri: basta cercare divisori fino alla radice quadrata, perché se n = a × b almeno uno dei due fattori è per forza ≤ √n. Questo tool prova 2, 3 e poi solo i candidati della forma 6k ± 1 (gli unici possibili primi oltre il 3), così la verifica è istantanea anche per numeri fino a mille miliardi. Se il numero non è primo, il divisore più piccolo trovato è sempre a sua volta un numero primo.
Il crivello di Eratostene, un algoritmo di 2.200 anni fa
Per generare l'elenco si usa il metodo del matematico greco Eratostene: si scrivono tutti i numeri fino al limite e si "setacciano" via i multipli di ogni primo trovato, partendo dal suo quadrato. Ciò che resta sono i numeri primi. Man mano che si sale diventano più rari: ce ne sono 25 fino a 100, 168 fino a 1.000 e 9.592 fino a 100.000 — eppure, come dimostrò Euclide, non finiscono mai.