Accueil

Orientation générale

Barre de recherche

DicoNombre

DicoMot Math

DicoCulture

Atlas des maths

Rubriques

Index alphabétique

Nouveautés

Actualités

Références

Édition du: 19/10/2022

M'écrire

Brèves de Maths

 

INDEX

 

Cribles

Types de premiers

Types de nombres

Nombres premiers – CRIBLES  

Cribles

Crible d'Ératosthène

Ératosthène programmation

Sundaram

Crible de la roue

Roue programmation

René Nève

Crible d'Atkin

Atkin programmation

Faites un double-clic pour un retour en haut de page

 

 

Types de CRIBLES

 

Un crible destiné à isoler les nombres premiers est un algorithme de tri qui élimine progressivement les nombres composés pour ne garder que les nombres premiers.

Revue des principaux cribles et accès vers leurs développements et programmation.

 

Ces algorithmes visent à connaitre tous les nombres premiers de 2 à une limite n. Une autre  préoccupation consiste à déterminer si un nombre n est premier (sans forcément connaitre la nature de ses voisins). C'est l'objet des tests de primalité.

Une autre idée, vaine à ce jour, consiste à trouver des formules qui encapsuleraient un maximum de nombres premiers.

  

 

Sommaire de cette page

>>> Le crible le plus connu – Ératosthène

>>> Divisibilité par 2, 3, et 5

>>> Divisibilité par 6 et 30

>>> Divisibilité par 4, 6, 12 et 60

>>> Optimisation

>>> Bilan

 

Débutants

Premiers

 

Glossaire

Premiers

 

 

Le crible le plus connu – Ératosthène

haut

 

À partir de la liste des nombres (cubes rouges en haut);

Une grille qui est percée toutes les deux positions bloque les nombres pairs.

La grille suivante bloque les multiples de 3.

Le nombre 4 a déjà été bloqué, on passe donc au 5.

Etc.

 

 

Les nombres premiers sont ceux qui subsistent en tête de grille: 2, 3, 5, 7, 11 …

 

Avec le 7, par exemple, on sait que le prochain nombre retenu par la grille sera 7 x 7 = 49, car les précédents (2x7 = 17, 3x7 = 21 et 5x7 = 35) ont déjà été retenus sur les grilles supérieures avec les nombres premiers: 2, 3 et 5.

 

 

Le crible d’Ératosthène imagé par une succession de grilles judicieusement percée

eratost

Voir Crible d'Ératosthène

 

Crible produisant tous les nombres premiers jusqu'à 121 = 11² (celui-ci étant composé !)

Il y a 30 nombres premiers de 1 à 121: 2, 3, 5, 7, 11, 13, 17, …113.

Les nombres à droite indiquent la quantité de nombres retenus sur cet étage jusqu'à 121.

 

Réalisation par programme

haut

 

Principe

Le crible d'Ératosthène  est facile à réaliser par programmation.

*      Énumérer les nombres: ici, sur la première ligne. Les nombres de 2 à 121 sont rangés dans la liste L.

*      Ne conserver que les non-pairs dans la liste L2.

*      Idem avec les non multiples de 3 dans L3. Etc.

Cette méthode illustre bien le principe de tamisage progressif, couche après couche.

On observe également que certains nombres sont analysés à plusieurs reprises, de couche en couche. Il est possible d'optimiser l'algorithme en réduisant certaines de ces répétitions.

 

Programme Maple

 

Explication détaillée de la ligne 2:

*      L2 := {   } : demande à ouvrir une suite de nombres nommée L2. On dit: déclaration de la suite L2.

*      := ce double symbole indique un rangement en mémoire. On dit: une affectation. Notez que ce n'est pas la marque de l'égalité comme dans 4 = 1 + 3.

*      for n in L do ... od : pour chaque n successifs de la liste L faire.

*      n mod 2 0: écriture commode qui indique que le reste de la division par 2 n'est pas nul.

*      if n mod 2 0 then …. fi: si le reste n'est pas nul, alors faire ce qui suit jusqu'à la marque de fin de la condition notée fi (le if à l'envers).

*      L2 := {op(L2), n}: demande de ranger n dans L2. On précise: tu reprends L2 (signifié par: op(L2) ) et tu y ajoutes le nombre n.

*      L2; avec un point-virgule, demande l'impression de L2

 

Voir Programmation du crible d'Ératosthène / ProgrammationIndex

 

 

 

Divisibilité par 2, 3, et 5

haut

 

Parmi tous les nombres, il est facile d'éliminer ceux qui sont divisibles par 2 et par 5. Il suffit d'un simple test sur l'unité.

Donc, élimination de tous les nombres terminés par 0, 2, 4, 5, 6 et 8.

  

Ce simple test élimine 60% des nombres.
72 nombres divisibles par 2 ou 5 jusqu'à 121.

 

Ne restent donc que les nombres terminés en 1, 3, 7 et 9 (Voir la ligne du 7 ci-dessus).

 

Un autre écrémage facile à effectuer consiste à tester la somme des chiffres. Si elle est divisible par 3, alors le nombre lui-même est divisible par 3.

 

Tous les cribles s'empressent d'éliminer tous ces nombres avant de tester des divisibilités plus difficiles à reconnaitre.

 

 

Ce petit test élimine 16 % des nombres rescapés du test précédent (n < 121).

 

Ne restent alors que 32 nombres parmi les 121:
7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97, 101, 103, 107, 109, 113, 119, 121.

 

 

 

Divisibilité par 6 et 30

haut

 

En considérant les nombres non divisibles par 2, 3 ou 5, on observe qu'ils sont tous voisins d'un multiple de 6.

 

 

Propriété

Un nombre premier est toujours voisin d'un multiple de 6 comme le montre cet exemple:

 

  Voir Barre magique des nombres premiers

 

 

 

Un bon moyen d'accélérer la recherche des nombres premiers consiste à ne considérer que les multiples de 6 et à analyser les deux voisins.

Voir Primorielle et recherche des nombres premiers /

Programme Python

 

Encore mieux, les examiner sur trois dizaines. En effet, avec 30 = 2 x 3 x 5, on observe l'effet marguerite visible sur cette roue à huit pétales spécifiques (languettes bleues). Chacun des pétales est voisin de pétales avec multiples de 6:

*    six pétales en couple (en 6k–1 et 6k+1) , et

*    deux pétales isolés, car un des voisins est en multiples de 5.

 

Cette propriété est exploitée pour réaliser le crible de la roue (wheel sieve). Seuls les nombres des pétales sont à examiner.

 

Propriété

Sur une marguerite à 30 pétales seuls 8 sont susceptibles de contenir des nombres premiers (à partir de 7).

Elles sont voisines de pétales contenant des multiples de 6.

Agrandir l'image

 

Voir Brève 818

 

 

Arithmétique modulaire: on se contente des restes …

 

La notion de divisibilité est fondamentale pour la recherche des nombres premiers. On note, qu'il est inutile de connaitre le résultat de la division. Seul le reste importe. S'il est nul, le nombre est divisible donc non premiers.

Ce besoin limité a conduit à développer une branche de la théorie des nombres dite arithmétique modulaire. Dire que le nombre 19 est "égal" à 5 modulo 7, veut dire que l'on retire le plus possibles de modules égaux à 7 dans 19 et que l'on conserve uniquement ce qui reste:
19 – 7 = 12; 12 – 7 = 5. On note: 19 ≡ 5 mod 7.

 

 

 

Divisibilité par 4, 6, 12 et 60

haut

 

Pour améliorer encore la vitesse de recherche, il faut faire appel à des propriétés profondes de la théorie des nombres.

Trouvé autour de l'an 2000, le crible d'Atkin est de ceux-là. Ce mathématicien a divisé les nombres premiers en trois ensembles selon leurs restes dans la division par 4, 6 ou 16 (Tableau).

Pour chacun de ces ensembles, il existe une propriété qui est spécifique des nombres premiers. Le crible ramasse aussi des nombres comme les carrés (49 = 7²) qu'il suffit de retirer.

 

 

Propriété

Par exemple, le nombre 17 divisé par 60 donne un reste de 17, par 12, un reste de 5, comme par 6 et il produit un reste égal à 1 lorsque divisé par 4.

On note: 17 ≡ 1760 ≡ 512 ≡ 56 ≡ 14

 

  Agrandir l'image

 

 

Optimisation

haut

 

Nous avons vu que l'algorithme de base du crible d'Ératosthène nécessite de reprendre les tests de divisibilité à de nombreuses reprises pour certains nombres, surtout lorsque ceux-ci deviennent grands.

La première idée, on l'a vu, consiste à réduire le champ d'analyse: crible de la roue

 

 

Certains algorithmes tentent d'éliminer un maximum de répétitions: cas du crible de Marouane Rhafli . Cet algorithme exploite la propriété que tout nombre composé impair est de la forme: n = p² + 2pk. Ex: 99 = 3² + 3 x 30

 

D'autres vont chercher des propriétés tout aussi subtiles de la théorie des nombres:

*      Crible de Sundaram

*      Crible d'Atkin (formes quadratiques)

  

 

Bilan

Les algorithmes de cribles nécessitent la mise en mémoire de tous les nombres premiers, ce qui limite leur intérêt dans le cas de très grands nombres du fait de disposer de mémoires de très grandes tailles.

Le travail sur ces algorithmes reste un très bon exercice d'apprentissage de la programmation.

Il existe encore des recherches d'optimisation, mais l'accent porte davantage sur la recherche de nombres premiers très grands car utilisés par les méthodes de cryptage.

Aujourd'hui de nombreux outils logiciels sont disponibles pour indiquer rapidement la primalité d'un nombre. Voir aussi mes tables

 

 

Haut de page

 

 

Retour

*      Nombres premiers

Suite

*      Crible d'Ératosthène

*      Crible de la roue

*      Méthode de René Nève

*      Nombres premiers en tableaux

*      Barre magique

*      Séquences en 6n

*      Crible d' Ératosthène

*      Nombres chanceux – Crible d'Ulam

*      Nombres premiersIndex

Voir

*      Liste de nombres premiers

*      Types de cribles

 

*      Crible de Moessner

*      Ératosthène

*      Nombres composés

*      Premiers en cercles et croix

*      Programmation du crible d'Ératosthène

*      Représentation des nombres

*      Spirale d'Ulam

Sites

*      Crible d'Ératosthène – Wikipédia

*       Théorie des cribles* – Wikipédia

*       Generation of primes – Wikipedia

*       Primes Numbers Sieves – Lakshmanan Subbiah

*      Proving primality – Chris Caldwell

*      Sublinear segmented prime sieve – Marouane Rhafli

*      An introduction to prime number sieves** - Jonathan Sorenson – pdf

*      Linear Prime-Number Sieves: a family tree – Paul Pritchard - 1985

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Premier/Crible.htm