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 (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 4x² + y² = n.
- Dans la deuxième classe, on compte le nombre de couples x > 0 et y > 0 solutions de 3x² + y² = n.
- Dans la troisième classe, on compte le nombre de couples x > 0 et y > 0 solutions de 3x² - y² = 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 p².
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.
