numbers Lista y Comprobador de Números Primos star

Cómo Funciona

La herramienta alterna entre dos algoritmos distintos, cada uno adecuado para una pregunta diferente. El modo Listar encuentra todos los primos hasta un límite usando la Criba de Eratóstenes, uno de los algoritmos más antiguos que todavía se usa a diario (atribuido al matemático griego Eratóstenes, siglo III a. C.). Empezando desde el 2, marca como compuesto cada múltiplo de 2, luego pasa al siguiente número sin marcar (el 3) y marca todos sus múltiplos, después al siguiente sin marcar (el 5), y así sucesivamente. Todo lo que sobrevive sin marcar al llegar a la raíz cuadrada del límite es primo. Un ejemplo pequeño: para cribar hasta 30, tacha los múltiplos de 2 (4, 6, 8, …), luego los múltiplos de 3 (6, 9, 12, …, algunos ya tachados), después los múltiplos de 5 (10, 15, …) — dado que 5×5=25 ≤ 30 pero 7×7=49 > 30, puedes detenerte ahí; lo que queda — 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — es la lista completa. Esto se ejecuta en tiempo O(n log log n), lo que significa que sigue siendo rápido incluso cuando el intervalo crece hasta cientos de miles.

El modo Comprobar responde una pregunta distinta — ¿es primo este número en concreto? — mediante división de prueba hasta la raíz cuadrada. Para comprobar si n es primo, basta con revisar los divisores desde 2 hasta √n. El razonamiento: si n = a × b con a y b mayores que √n, entonces a × b sería mayor que n, lo cual es imposible. Por lo tanto, al menos uno de los dos factores debe ser √n o menor, y se encontrará antes de que termine el bucle. Ejemplo: para comprobar 97, solo hace falta probar la divisibilidad entre 2, 3, 5 y 7 (ya que 9² = 81 ≤ 97 pero 10² = 100 > 97) — ninguno lo divide exactamente, así que 97 es primo.

Qué Debes Saber

Los dos modos existen porque tienen compensaciones distintas: la criba es eficiente para producir muchos primos a la vez, pero desperdicia memoria y tiempo si solo te interesa un número cercano a un límite enorme; la división de prueba es eficiente para una sola comprobación, pero demasiado lenta si se repite para cada número de un intervalo grande uno por uno. Elegir la adecuada para cada tarea es precisamente lo que ofrece esta herramienta con ambos modos.

• El 1 queda excluido de los primos por definición y convención — tiene un solo divisor, no dos, lo cual rompería la unicidad de la factorización en primos si se permitiera.
• El 2 es el único primo par; cualquier otro número par es divisible entre 2 y, por tanto, compuesto.
• A medida que los números crecen, los primos se vuelven más escasos en promedio, pero nunca dejan de aparecer — Euclides demostró hace más de dos mil años que hay infinitos.