Crible d'Atkin
- Crible d'Atkin
-
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.
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, avec x > y, 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.
Références
A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (1999), 1023-1030.
Liens externes
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Crible d'Atkin de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Crible d’Atkin — Crible d Atkin 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… … Wikipédia en Français
Crible d'Erathostene — Crible d Ératosthène Le crible d Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C est l ancêtre du crible d Atkin qui est plus rapide mais plus complexe. Sommaire 1… … Wikipédia en Français
Crible d'Erathostène — Crible d Ératosthène Le crible d Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C est l ancêtre du crible d Atkin qui est plus rapide mais plus complexe. Sommaire 1… … Wikipédia en Français
Crible d'Eratosthene — Crible d Ératosthène Le crible d Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C est l ancêtre du crible d Atkin qui est plus rapide mais plus complexe. Sommaire 1… … Wikipédia en Français
Crible d'Eratosthène — Crible d Ératosthène Le crible d Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C est l ancêtre du crible d Atkin qui est plus rapide mais plus complexe. Sommaire 1… … Wikipédia en Français
Crible d'Érathostène — Crible d Ératosthène Le crible d Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C est l ancêtre du crible d Atkin qui est plus rapide mais plus complexe. Sommaire 1… … Wikipédia en Français
Crible d’Ératosthène — Crible d Ératosthène Le crible d Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C est l ancêtre du crible d Atkin qui est plus rapide mais plus complexe. Sommaire 1… … Wikipédia en Français
Crible (Mathématiques) — Pour les articles homonymes, voir Crible. Article détaillé : Théorie des cribles. En mathématiques, les cribles sont des techniques algorithmiques permettant d approcher le cardinal de certains ensembles de nombres. D autre part, ils… … Wikipédia en Français
Crible d'Ératosthène — Le crible d Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C est l ancêtre du crible d Atkin qui est plus rapide mais plus complexe. Sommaire 1 Algorithme 2 Exemples d… … Wikipédia en Français
Crible (mathématiques) — Pour les articles homonymes, voir Crible. Article détaillé : Théorie des cribles. En mathématiques, les cribles sont des techniques algorithmiques permettant d approcher le cardinal de certains ensembles de nombres. D autre part, ils… … Wikipédia en Français
