Crible d'Atkin
Un article de Wikipédia, l'encyclopédie libre.
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.
[modifier] Algorithme
Quelques variables sont nécessaires :
- Le tableau des nombres premiers que l'on a trouvé, que l'on initialise avec les nombres premiers inférieurs à soixante.
- Trois tableaux contenant les nombres qu'il reste à tester, et qui ont certains restes dans la division 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 (notons que les nombres avec certains restes sont ignorés) :
- 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 solutions de 3x2 - y2 = n.
- Si le compte est impair, 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 restant dans la liste des nombres premiers.
[modifier] Références
A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (1999), 1023-1030.
