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. Le crible d'Atkin est plus rapide mais plus complexe. L'algorithme procède par élimination : il s'agit de supprimer d'une table des entiers de 2 à N tous les multiples d'un entier (autres que lui-même). En supprimant tous ces multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier à part 1 et eux-mêmes, et qui sont donc les nombres premiers. On commence par rayer les multiples de 2, puis les multiples de 3 restants, puis les multiples de 5 restants, et ainsi de suite en rayant à chaque fois tous les multiples du plus petit entier restant. On peut s'arrêter lorsque le carré du plus petit entier restant est supérieur au plus grand entier restant, car dans ce cas, tous les non-premiers ont déjà été rayés précédemment. À la fin du processus, tous les entiers qui n'ont pas été rayés sont les nombres premiers inférieurs à N. L'animation ci-dessous illustre le crible d'Ératosthène pour N=120 : Remarque: si un nombre n est composé, alors n=n1n2, avec nécessairement l'un au moins des diviseurs ni plus petit que . C'est pourquoi dans le crible ci-dessus où l'on a choisi 120 puisque 121=112, on s'arrête après avoir trouvé les multiples de 7. Le crible d'Ératosthène peut être mis en œuvre de façon classique ou récursive, mais aussi sous la forme d'une méthode pipe-line. Dans une version classique, on transcrit ainsi l'algorithme : Fonction Eratosthène(Limite) L = tableau de booléen de taille Limite, initialisé à Vrai L[1] = Faux Pour i de 2 à Limite Si L[i] Pour j de ii à Limite par pas de i on peut commencer à ii car tous les multiples de i inférieurs à ii ont déjà été rayés L[j] = Faux Fin pour Fin si Fin pour Retourner L Fin fonction Comme dans l'animation ci-dessus, on peut optimiser le code précédent en arrêtant la boucle Pour i une fois ii>Limite puisque l'on ne rentrera plus dans la boucle Pour j et en se contentant d'afficher les indices de L contenant Vrai.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.