Concept
Le crible d'Atkin est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C'est une version améliorée du crible d'Ératosthène, il fut créé en 1999 par A. O. L. Atkin et Daniel J. Bernstein. Le crible d'Ératosthène consiste à trouver les valeurs pouvant se réduire à la forme quadratique binaire réduite x⋅y (produit de deux entiers strictement supérieurs à 1). Le crible d'Atkin consiste lui à dénombrer les valeurs d'une forme quadratique binaire non-réduite. Par exemple, un entier sans facteur carré p qui est congru à 1 modulo 4 est premier si et seulement si l'équation 4x + y = p admet un nombre impair de solutions positives (x, y). Quelques variables sont nécessaires : le tableau des nombres premiers que l'on a trouvés, que l'on initialise avec les nombres premiers inférieurs à soixante ; trois tableaux contenant les nombres qu'il reste à tester, selon le reste dans la division euclidienne par soixante ; ils sont initialisés avec tous les entiers entre soixante et le dernier nombre qui nous intéresse, tel que le reste modulo soixante est dans l'une de ces trois listes (on ne considère que les restes premiers avec 60) : reste valant 1, 13, 17, 29, 37, 41, 49, ou 53, reste valant 7, 19, 31, ou 43, reste valant 11, 23, 47, ou 59. Après, pour chaque nombre n restant : dans la première classe, on compte le nombre de couples x > 0 et y > 0 solutions de 4x2 + y2 = n ; dans la deuxième classe, on compte le nombre de couples x > 0 et y > 0 solutions de 3x2 + y2 = n ; dans la troisième classe, on compte le nombre de couples x > 0 et y > 0, avec x > y, solutions de 3x2 – y2 = n ; si le compte est pair, on supprime n de la liste. Ensuite, on applique un crible d'Ératosthène modifié : pour chaque nombre premier p supérieur à 7, on supprime tous les multiples de p2. Enfin, on place les nombres restants dans la liste des nombres premiers. Avec cet algorithme, la recherche des nombres premiers inférieurs à N a une complexité en temps en o(N) et une complexité en mémoire en O(Nα) avec α < 1.