Tamis d'Eratosthène - Sieve of Eratosthenes

Tamis d'Eratosthène : étapes de l'algorithme pour les nombres premiers inférieurs à 121 (y compris l'optimisation du départ à partir du carré des nombres premiers).

En mathématiques , le tamis d'Eratosthène est un ancien algorithme permettant de trouver tous les nombres premiers jusqu'à une limite donnée.

Il le fait en marquant de manière itérative comme composites (c'est-à-dire non premiers) les multiples de chaque nombre premier, en commençant par le premier nombre premier, 2. Les multiples d'un nombre premier donné sont générés comme une séquence de nombres à partir de ce nombre premier, avec une différence constante entre eux qui est égal à ce nombre premier. C'est la distinction clé du tamis par rapport à l'utilisation de la division d'essai pour tester séquentiellement chaque numéro candidat pour la divisibilité par chaque nombre premier. Une fois que tous les multiples de chaque nombre premier découvert ont été marqués comme composés, les nombres non marqués restants sont des nombres premiers.

La première référence connue au tamis ( grec ancien : κόσκινον Ἐρατοσθένους , kóskinon Eratosthénous ) se trouve dans l ' Introduction à l' arithmétique de Nicomaque de Gérasa , au début du IIe siècle . Livre CE, qui le décrit et l'attribue à Eratosthène de Cyrène , un 3e cent. Mathématicien grec avant notre ère .

L'un des nombreux tamis de nombres premiers , c'est l'un des moyens les plus efficaces de trouver tous les plus petits nombres premiers. Il peut être utilisé pour trouver des nombres premiers dans des progressions arithmétiques .

Aperçu

Tamisez les deux et tamisez les trois :
le tamis d'Eratosthène.
Quand les multiples subliment,
les nombres qui restent sont premiers.

Anonyme

Un nombre premier est un nombre naturel qui a exactement deux diviseurs naturels distincts : le nombre 1 et lui-même.

Pour trouver tous les nombres premiers inférieurs ou égaux à un entier donné n par la méthode d'Eratosthène :

  1. Créez une liste d'entiers consécutifs de 2 à n : (2, 3, 4, ..., n ) .
  2. Initialement, soit p égal à 2, le plus petit nombre premier.
  3. Énumérez les multiples de p en comptant par incréments de p de 2 p à n , et marquez-les dans la liste (ce seront 2 p , 3 p , 4 p , ... ; le p lui-même ne doit pas être marqué).
  4. Trouvez le plus petit nombre dans la liste supérieur à p qui n'est pas marqué. S'il n'y avait pas un tel numéro, arrêtez. Sinon, laissez p être maintenant égal à ce nouveau nombre (qui est le prochain nombre premier) et répétez à partir de l'étape 3.
  5. Lorsque l'algorithme se termine, les nombres restants non marqués dans la liste sont tous les nombres premiers inférieurs à n .

L'idée principale ici est que chaque valeur donnée à p sera première, car si elle était composée, elle serait marquée comme un multiple d'un autre nombre premier plus petit. Notez que certains des nombres peuvent être marqués plus d'une fois (par exemple, 15 sera marqué à la fois pour 3 et 5).

En guise de raffinement, il suffit de marquer les nombres à l'étape 3 à partir de p 2 , car tous les plus petits multiples de p auront déjà été marqués à ce point. Cela signifie que l'algorithme est autorisé à mettre fin à l' étape 4 lorsque p 2 est supérieur à n .

Un autre raffinement consiste à répertorier initialement uniquement les nombres impairs (3, 5, ..., n ) et à compter par incréments de 2 p à partir de p 2 à l'étape 3, marquant ainsi uniquement les multiples impairs de p . Cela apparaît en fait dans l'algorithme d'origine. Ceci peut être généralisé avec roue factorisation , formant la liste initiale que des numéros premiers entre eux avec les premiers nombres premiers et pas seulement de bric (c. -à- nombres premiers entre eux avec 2), et le comptage des incréments en conséquence ajustés de sorte que seuls les multiples de p sont générés qui sont premiers entre eux avec ces petits nombres premiers, en premier lieu.

Exemple

Pour trouver tous les nombres premiers inférieurs ou égaux à 30, procédez comme suit.

Tout d'abord, générez une liste d'entiers de 2 à 30 :

 2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Le premier nombre de la liste est 2 ; rayez tous les 2 nombres de la liste après 2 en comptant à partir de 2 par incréments de 2 (ce seront tous les multiples de 2 dans la liste) :

 2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Le numéro suivant dans la liste après 2 est 3 ; rayez tous les 3 nombres de la liste après 3 en comptant à partir de 3 par incréments de 3 (ce seront tous les multiples de 3 dans la liste) :

 2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Le numéro suivant non encore barré dans la liste après 3 est 5; rayer tous les 5 nombres de la liste après 5 en comptant à partir de 5 par incréments de 5 (c'est-à-dire tous les multiples de 5) :

 2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Le numéro suivant non barré dans la liste après 5 est 7 ; la prochaine étape serait de rayer tous les 7 nombres de la liste après 7, mais ils sont tous déjà barrés à ce stade, car ces nombres (14, 21, 28) sont également des multiples de plus petits nombres premiers car 7 × 7 est plus grand supérieur à 30. Les nombres non barrés à ce stade de la liste sont tous les nombres premiers inférieurs à 30 :

 2  3     5     7           11    13          17    19          23                29

Algorithme et variantes

Pseudocode

Le crible d'Eratosthène peut s'exprimer en pseudocode , comme suit :

algorithm Sieve of Eratosthenes is
    input: an integer n > 1.
    output: all prime numbers from 2 through n.

    let A be an array of Boolean values, indexed by integers 2 to n,
    initially all set to true.
    
    for i = 2, 3, 4, ..., not exceeding n do
        if A[i] is true
            for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
                A[j] := false

    return all i such that A[i] is true.

Cet algorithme produit tous les nombres premiers non supérieurs à n . Il comprend une optimisation commune, qui consiste à commencer à énumérer les multiples de chaque premier i à partir de i 2 . La complexité temporelle de cet algorithme est O ( n log log n ) , à condition que la mise à jour du tableau soit une opération O (1) , comme c'est généralement le cas.

Tamis segmenté

Comme le note Sorenson, le problème avec le tamis d'Eratosthène n'est pas le nombre d'opérations qu'il effectue mais plutôt ses besoins en mémoire. Pour n grand , la plage de nombres premiers peut ne pas tenir en mémoire ; pire, même pour un n modéré , son utilisation du cache est très sous-optimale. L'algorithme parcourt l'ensemble du tableau A , ne présentant pratiquement aucune localité de référence .

Une solution à ces problèmes est offerte par des tamis segmentés , où seules des portions de la gamme sont tamisées à la fois. Ceux-ci sont connus depuis les années 1970 et fonctionnent comme suit :

  1. Divisez la plage 2 à n en segments d'une certaine taille Δ ≤ n .
  2. Trouvez les nombres premiers dans le premier segment (c'est-à-dire le plus bas) en utilisant le tamis ordinaire.
  3. Pour chacun des segments suivants, dans l'ordre croissant, m étant la valeur la plus élevée du segment, trouvez les nombres premiers qu'il contient comme suit :
    1. Mettre en place un tableau de booléens de taille Δ , et
    2. Marquer comme non-prime les positions dans le réseau correspondant aux multiples de chaque premier pm trouvé à ce jour, en calculant le plus petit multiple de p entre m - Δ et m , et énumérant ses multiples par pas de p , comme d' habitude. Les positions restantes correspondent aux nombres premiers dans le segment, puisque le carré d'un nombre premier dans le segment n'est pas dans le segment (pour k 1 , on a ).

Si Δ est choisi égal à n , la complexité spatiale de l'algorithme est O ( n ) , tandis que la complexité temporelle est la même que celle du tamis régulier.

Pour les plages avec une limite supérieure n si grande que les premiers de tamisage inférieurs à n comme requis par le tamis segmenté par page d'Eratosthène ne peuvent pas tenir en mémoire, un tamis plus lent mais beaucoup plus compact comme le tamis de Sorenson peut être utilisé à la place.

Tamis incrémental

Une formulation incrémentale du tamis génère des nombres premiers indéfiniment (c'est-à-dire sans borne supérieure) en entrelaçant la génération de nombres premiers avec la génération de leurs multiples (de sorte que les nombres premiers peuvent être trouvés dans les écarts entre les multiples), où les multiples de chaque nombre premier p sont générés directement en comptant à partir du carré du nombre premier par incréments de p (ou 2 p pour les nombres premiers impairs). La génération ne doit être initiée que lorsque le carré du premier est atteint, afin d'éviter des effets néfastes sur l'efficacité. Il peut être exprimé symboliquement sous le paradigme du flux de données comme

primes = [2, 3, ...] \ [[p², p²+p, ...] for p in primes],

en utilisant la compréhension liste notation avec \dénotant soustraction ensemble des progressions arithmétiques de nombres.

Des primes peuvent également être produites en tamisant de manière itérative les composites grâce à des tests de divisibilité par des primes séquentielles, une prime à la fois. Ce n'est pas le tamis d'Ératosthène mais est souvent confondu avec lui, même si le tamis d'Ératosthène génère directement les composites au lieu de les tester. La division d'essai a une complexité théorique pire que celle du crible d'Ératosthène dans la génération de gammes de nombres premiers.

Lors du test de chaque nombre premier, l' algorithme de division d'essai optimal utilise tous les nombres premiers ne dépassant pas sa racine carrée, tandis que le tamis d'Eratosthène produit chaque composite à partir de ses facteurs premiers uniquement et obtient les nombres premiers "gratuitement", entre les composites. Le code de tamis fonctionnel de 1975 largement connu par David Turner est souvent présenté comme un exemple du tamis d'Eratosthène mais est en fait un tamis de division d'essai sous-optimal.

Complexité algorithmique

Le tamis d'Eratosthène est un moyen populaire de comparer les performances d'un ordinateur. La complexité temporelle du calcul de tous les nombres premiers inférieurs à n dans le modèle de machine à accès aléatoire est de O ( n log log n ) opérations, conséquence directe du fait que la série harmonique principale s'approche asymptotiquement de log log n . Il a cependant une complexité temporelle exponentielle en ce qui concerne la taille d'entrée, ce qui en fait un algorithme pseudo-polynomial . L'algorithme de base nécessite O ( n ) de mémoire.

La complexité en bits de l'algorithme est de O ( n (log n ) (log log n ) ) opérations sur bits avec une exigence de mémoire de O ( n ) .

La version segmentée de page normalement implémentée a la même complexité opérationnelle de O ( n log log n ) que la version non segmentée mais réduit les besoins en espace à la taille très minimale de la page de segment plus la mémoire requise pour stocker les nombres premiers de base inférieurs à la racine carrée de la plage utilisée pour éliminer les composites de segments de page successifs de taille O ( n/log n) .

Une version segmentée spéciale (rarement, voire jamais, mise en œuvre) du tamis d'Ératosthène, avec des optimisations de base, utilise O ( n ) opérations et O (nlog log n/log n) bits de mémoire.

L'utilisation de la notation grand O ignore les facteurs constants et les décalages qui peuvent être très importants pour les plages pratiques : le tamis de la variation d'Eratosthène connu sous le nom de tamis à roue de Pritchard a une performance O ( n ) , mais sa mise en œuvre de base nécessite soit un algorithme « un grand tableau » ce qui limite sa plage utilisable à la quantité de mémoire disponible, sinon il doit être segmenté par page pour réduire l'utilisation de la mémoire. Lorsqu'il est implémenté avec une segmentation de page afin d'économiser de la mémoire, l'algorithme de base nécessite encore environ O (m/log n) bits de mémoire (beaucoup plus que l'exigence du tamis segmenté de base de page d'Eratosthène utilisant O (n/log n) bits de mémoire). Le travail de Pritchard a réduit les besoins en mémoire au prix d'un grand facteur constant. Bien que le tamis à roue résultant ait desperformances O ( n )et une exigence de mémoire acceptable, il n'est pas plus rapide qu'un tamis de base raisonnablement factorisé par roue d'Eratosthène pour des plages de tamisage pratiques.

le tamis d'Euler

La preuve d' Euler de la formule du produit zêta contient une version du tamis d'Eratosthène dans laquelle chaque nombre composé est éliminé exactement une fois. Le même tamis a été redécouvert et observé comme prenant un temps linéaire par Gries & Misra (1978) . Il commence aussi par une liste de nombres de 2 à n dans l'ordre. À chaque étape, le premier élément est identifié comme le prochain premier, est multiplié par chaque élément de la liste (en commençant ainsi par lui-même) et les résultats sont marqués dans la liste pour une suppression ultérieure. L'élément initial et les éléments marqués sont ensuite retirés de la séquence de travail, et le processus est répété :

 [2] (3) 5  7  9  11  13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79  ...
 [3]    (5) 7     11  13    17 19    23 25    29 31    35 37    41 43    47 49    53 55    59 61    65 67    71 73    77 79  ...
 [4]       (7)    11  13    17 19    23       29 31       37    41 43    47 49    53       59 61       67    71 73    77 79  ...
 [5]             (11) 13    17 19    23       29 31       37    41 43    47       53       59 61       67    71 73       79  ...
 [...]

Ici, l'exemple est montré à partir des cotes, après la première étape de l'algorithme. Ainsi, à la k ème étape tous les multiples restants du k ème nombre premier sont retirés de la liste, qui ne contiendra plus que des nombres premiers entre eux avec les k premiers nombres premiers (cf. factorisation en roue ), de sorte que la liste commencera par le prochain premier, et tous les nombres qu'il contient sous le carré de son premier élément seront également premiers.

Ainsi, lors de la génération d'une séquence bornée de nombres premiers, lorsque le prochain nombre premier identifié dépasse la racine carrée de la limite supérieure, tous les nombres restants dans la liste sont premiers. Dans l'exemple donné ci-dessus, cela est obtenu en identifiant 11 comme nombre premier suivant, donnant une liste de tous les nombres premiers inférieurs ou égaux à 80.

Notez que les nombres qui seront rejetés par une étape sont toujours utilisés lors du marquage des multiples de cette étape, par exemple, pour les multiples de 3, c'est 3 × 3 = 9 , 3 × 5 = 15 , 3 × 7 = 21 , 3 × 9 = 27 , ..., 3 × 15 = 45 , ..., il faut donc faire attention à cela.

Voir également

Les références

Liens externes