Criba de primalidad moderna que usa aritmética modular y condiciones de residuos cuadráticos para identificar candidatos hasta un límite N, seguida de eliminar múltiplos de cuadrados para dejar primos; a menudo más rápida que la clásica para límites grandes optimizados.

Principio

Aplicar reglas basadas en x^2 + y^2, 3x^2 − y^2 y 3x^2 + y^2 módulo pequeños para alternar bits de candidaturas de enteros que satisfacen ciertas congruencias, y luego eliminar múltiplos de cuadrados para finalizar la lista de primos.

Demostración

Para N ≤ 50 el algoritmo alterna candidatos según pequeños pares x,y que satisfacen las congruencias cuadráticas; tras alternarlos y eliminar múltiplos de cuadrados quedan candidatos como 5,7,11,13,17,19,23,29,31,37,41,43,47.

Aplicación incorrecta

Implementar las reglas de Atkin incorrectamente (condiciones de congruencia erróneas u omisión de la eliminación de cuadrados), o usar Atkin para N muy pequeño donde la sobrecarga lo hace más lento que Eratóstenes.

Consecuencia

Bien implementado y afinado, Atkin puede ofrecer mejores constantes asintóticas y comportamiento de caché para rangos de criba muy grandes, produciendo una lista correcta de primos tras eliminar cuadrados y validar.

Inversión

La reversión es fiarse únicamente del alternado de congruencias sin la etapa final de eliminación de cuadrados — eso produce muchos candidatos pseudoprimos y una lista incorrecta.

Límite

Atkin está destinado a enumerar primos hasta una gran cota N con implementación cuidadosa; requiere manejar correctamente las condiciones de residuos cuadráticos y no es ventajoso para intervalos pequeños o con mala localidad de memoria.

Tensión semántica

Compite con variantes optimizadas de Eratóstenes y con tests probabilísticos o deterministas de primalidad; Atkin enfatiza reglas de congruencia aritmética que reducen trabajo pero intercambian complejidad de implementación y constantes.

Síntesis

Atkin refina el cribado usando condiciones cuadráticas modulares para preseleccionar candidatos y luego eliminar múltiplos de cuadrados, ofreciendo un cribado teóricamente más rápido para N grandes cuando se implementa con optimización.