Criba de Atkin
# Criba de Atkin

La criba de Atkin es un algoritmo rápido y moderno empleado en matemática para hallar todos los números primos menores o iguales que un número natural dado. Es una versión optimizada de la criba de Eratóstenes, pero realiza algo de trabajo preliminar y no tacha los múltiplos de los números primos, sino concretamente los múltiplos de los cuadrados de los primos. Fue ideada por A. O. L. Atkin y Daniel J. Bernstein.

## Algoritmo

Así funciona el algoritmo:

* Todos los restos son módulo 60, es decir, se divide el número entre 60 y se toma el resto.
* Todos los números, incluidos x e y, son enteros positivos.
* Invertir un elemento de la lista de la criba significa cambiar el valor ("primo" o "no primo") al valor opuesto.
* Crear una lista de resultados, compuesta por 2, 3 y 5.
* Crear una lista de la criba con una entrada por cada entero positivo; todas las entradas deben marcarse inicialmente como "no primos".
* Para cada entrada en la lista de la criba:
   * Si la entrada es un número con resto 1, 13, 17, 29, 37, 41, 49 o 53, se invierte tantas veces como soluciones posibles hay para $4x^2$ + $y^2$ = entrada.
   * Si la entrada es un número con resto 7, 19, 31 o 43, se invierte tantas veces como soluciones posibles hay para $3x^2$ + $y^2$ = entrada.
   * Si la entrada es un número con resto 11, 23, 47 o 59, se invierte tantas veces como soluciones posibles hay para $3x^2$ - $y^2$ = entrada con la restricción x > y.
   * Si la entrada tiene otro resto, se ignora.
* Se empieza con el menor número de la lista de la criba.
* Se toma el siguiente número de la lista de la criba marcado como "primo".
* Se incluye el número en la lista de resultados.
* Se eleva el número al cuadrado y se marcan todos los múltiplos de ese cuadrado como "no primos".
* Repetir los pasos 5 a 8.

## Pseudocódigo

Este pseudocódigo indica una versión sencilla del algoritmo:

Este pseudocódigo está así escrito para aumentar la claridad, pero los cálculos redundantes hacen que sea más lento que la criba de Eratóstenes. Para mejorar su eficiencia, se deben emplear métodos más rápidos para hallar las soluciones de las tres ecuaciones. Para ello, se puede utilizar la identidad $(x+1)^{2}=x^{2}+2x+1$ para no tener que calcular el cuadrado de x e y, y calcular el módulo de las tres funciones cuadráticas a partir del módulo de x e y, tal como viene en las siguientes tablas:

$4x^{2}+y^{2}$

| y\x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| - | - | - | - | - | - | - | - | - | - | - | - | - |
| 0 | 0 | 4 | 4 | 0 | 4 | 4 | 0 | 4 | 4 | 0 | 4 | 4 |
| 1 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 |
| 2 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 |
| 3 | 9 | 1 | 1 | 9 | 1 | 1 | 9 | 1 | 1 | 9 | 1 | 1 |
| 4 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 |
| 5 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 |
| 6 | 0 | 4 | 4 | 0 | 4 | 4 | 0 | 4 | 4 | 0 | 4 | 4 |
| 7 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 |
| 8 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 |
| 9 | 9 | 1 | 1 | 9 | 1 | 1 | 9 | 1 | 1 | 9 | 1 | 1 |
| 10 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 |
| 11 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 |

$3x^{2}+y^{2}$

| y\x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| - | - | - | - | - | - | - | - | - | - | - | - | - |
| 0 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 |
| 1 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 |
| 2 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 |
| 3 | 9 | 0 | 9 | 0 | 9 | 0 | 9 | 0 | 9 | 0 | 9 | 0 |
| 4 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 |
| 5 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 |
| 6 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 |
| 7 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 |
| 8 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 |
| 9 | 9 | 0 | 9 | 0 | 9 | 0 | 9 | 0 | 9 | 0 | 9 | 0 |
| 10 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 |
| 11 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 |

$3x^{2}-y^{2}$

| y\x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| - | - | - | - | - | - | - | - | - | - | - | - | - |
| 0 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 |
| 1 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 |
| 2 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 |
| 3 | 3 | 6 | 3 | 6 | 3 | 6 | 3 | 6 | 3 | 6 | 3 | 6 |
| 4 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 |
| 5 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 |
| 6 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 |
| 7 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 |
| 8 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 |
| 9 | 3 | 6 | 3 | 6 | 3 | 6 | 3 | 6 | 3 | 6 | 3 | 6 |
| 10 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 |
| 11 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 |

## Explicación

El algoritmo ignora cualquier número divisible por 2, 3 o 5. Todos los números con resto, módulo 60, igual a 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56 o 58 son pares y por tanto compuestos. Los de resto 3, 9, 15, 21, 27, 33, 39, 45, 51 o 57 son divisibles por 3 y por tanto compuestos. Finalmente, los de resto 5, 25, 35 o 55 son divisibles entre 5 y por tanto compuestos. Todos estos restos son ignorados.

Todos los números con resto, módulo 60, igual a 1, 13, 17, 29, 37, 41, 49 o 53 tienen un resto, módulo 4, de 1. Estos números son primos si y solamente si el número de soluciones de $4x^2$ + $y^2$ = n es impar y el número es libre de cuadrados (demostrado como "teorema 6.1" en).

Todos los números con resto, módulo 60, igual a 7, 19, 31 o 43 tienen un resto, módulo 6, de 1. Estos números son primos si y solamente si el número de soluciones de $3x^2$ + $y^2$ = n es impar y el número es libre de cuadrados (demostrado como "teorema 6.2" en).

Todos los números con resto, módulo 60, de 11, 23, 47 o 59 tienen un resto, módulo 12, de 11. Estos números son primos si y solamente si el número de soluciones de $3x^2$ − $y^2$ = n es impar y el número es libre de cuadrados (demostrado como "teorema 6.3" en).

Ninguno de los candidatos a primos es divisible entre 2, 3 o 5, por lo que no puede ser divisible entre sus cuadrados. Esta es la razón por la que las comprobaciones de si un número es libre de cuadrados no incluyen los casos $2^2,$ $3^2$ y $5^2.$

## Complejidad computacional

Esta criba obtiene los números primos hasta N mediante O(N/log log N) operaciones con solamente $N^{1/2+o(1)}$ bits de memoria. Esto es ligeramente mejor que la criba de Eratóstenes, que requiere O(N) operaciones y $O(N^{1/2}(log$ log N)/log N) bits de memoria. Estas complejidades computacionales asintóticas ya incluyen algunas optimizaciones sencillas.

## Apéndice

Las dos primeras ecuaciones que se utilizan para determinar la primalidad de un número tras sus comprobaciones modulares son ecuaciones de elipses. Pueden reescribirse en la forma estándar dividiendo los dos miembros de la ecuación entre n, donde n es la entrada cuya primalidad se quiere determinar. Esta forma facilitaría la implementación de un test.

