Crible d'Atkin
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (Tableau peut avoir plusieurs sens suivant le contexte employé :) 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 (La division est une loi de composition qui à deux nombres associe le produit du premier par l'inverse du second. Si un nombre est non nul, la...) par soixante. Ils sont initialisés avec tous les entiers entre soixante et le dernier nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) qui nous intéresse, tel que le reste modulo ( En arithmétique modulaire, on parle de nombres congrus modulo n Le terme modulo peut aussi être associé à d'autres formes de congruence En informatique, le...) 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 (Dans un moyen de transport (avion, train ou bateau), la première classe est la classe la plus confortable et celle offrant généralement le plus de...), 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 (Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs (qui sont alors 1 et lui-même). Cette définition exclut 1, qui n'a qu'un...) p supérieur à 7, on supprime tous les multiples de p2.

Enfin, on place les nombres restant dans la liste des nombres premiers.

Page générée en 0.021 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique