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.[1]​ Así funciona el algoritmo: 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 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: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.Esta criba obtiene los números primos hasta N mediante O(N/log log N) operaciones con solamente N1/2+o(1) bits de memoria.[1]​ Estas complejidades computacionales asintóticas ya incluyen algunas optimizaciones sencillas.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.