Números primos
Comprueba al instante si un número es primo (y encuentra su divisor más pequeño si no lo es), o genera la lista completa de números primos hasta 100.000.
Cómo comprobar si un número es primo
Un número es primo cuando tiene exactamente dos divisores: 1 y él mismo. Para comprobarlo no hace falta probar todos los números: basta con buscar divisores hasta la raíz cuadrada, porque si n = a × b, al menos uno de los dos factores tiene que ser ≤ √n. Esta herramienta prueba el 2 y el 3, y luego solo los candidatos de la forma 6k ± 1 (los únicos primos posibles más allá del 3), así que la comprobación es instantánea incluso con números de hasta un billón. Cuando el número no es primo, el divisor más pequeño encontrado es siempre, a su vez, un número primo.
La criba de Eratóstenes, un algoritmo de hace 2.200 años
La lista se genera con el método del matemático griego Eratóstenes: escribes todos los números hasta el límite y luego vas «cribando» los múltiplos de cada primo que encuentras, empezando por su cuadrado. Lo que sobrevive es primo. Los primos son cada vez más raros a medida que subes: hay 25 por debajo de 100, 168 por debajo de 1.000 y 9.592 por debajo de 100.000 y, aun así, como demostró Euclides, no se acaban nunca.