Intentaré proporcionar una explicación simplificada de Atkin’s Sieve aquí. Asumiré que estás familiarizado con el Tamiz de Eratóstenes, y procederé a elaborar las optimizaciones que proporciona el método de Atkin.
Sin embargo, dado que esta es una explicación simplificada, no profundizaré demasiado en la teoría de números detrás del algoritmo. Sin embargo, es necesario comprender que el método se basa en una propiedad del resto de los números cuando se divide por 60. En particular, si excluimos los números que no son divisibles por 2, 3 o 5, podemos separar los números restantes en tres categorías a partir de las cuales la primalidad se puede determinar de la siguiente manera:
- Contando el número de soluciones para una forma cuadrática particular (según la categoría)
- Si el número de soluciones es impar, entonces tenemos que cualquier factor (no trivial) del número debe ser un cuadrado perfecto.
En el segundo punto se encuentra la clave de este algoritmo. Una vez que hemos completado esta inicialización primaria del tamiz, hemos eliminado de nuestra consideración cada número que tiene factores que no son cuadrados perfectos. Por lo tanto, en lugar de proceder a iterar a través del tamiz, eliminando múltiplos de 7,11,13 … como haríamos en el Tamiz de Eratóstenes, en su lugar verificamos solo múltiplos de 49,121,169 …
- ¿Cuál es la correlación entre las matemáticas y la informática? ¿Por qué es necesario?
- ¿Es posible escribir un programa para tabular la cantidad de tiempo que llevaría ver todos los programas en la lista instantánea de Netflix?
- Una máquina de Turing tiene una cantidad infinita de memoria, que no es posible en la vida real. ¿Por qué sigue siendo un buen modelo?
- ¿Pueden los lenguajes naturales ser completamente modelados por las máquinas de Turing?
- ¿Por qué es importante para un programador tener un buen dominio de los conceptos matemáticos?
Dado que sabemos que la raíz cuadrada del número limitante proporciona un límite superior en los factores potenciales de cualquier número por debajo de eso (este es un concepto retenido del tamiz de Eratóstenes), esto reduce drásticamente el número de iteraciones necesarias para eliminar los números compuestos .
Ahora que tenemos esos antecedentes en teoría de números, podemos interpretar fácilmente el algoritmo. Para x e y en rangos suficientes, encontramos soluciones para cada una de las formas cuadráticas correspondientes, y luego simplemente procedemos a eliminar los factores al cuadrado.
Para ver las pruebas de Atkin de estas propiedades en la teoría de números, vea Prime Sieves Using Binary Quadratic Forms
