algorithmes nombres premiers
bonjours a tous,
Je voudrais faire un algorithme pour extraire tous les nombres premiers inferieurs ou egaux a N.
Naivement, j'avais commencé par faire un algorithme récursif... c'est a dire
qu'il connaissait les nombres premiers suivant : {2,3,5}
puis il faisait une boucle qui pour chaque nombre essayait de diviser par chaque nombre premier déja connu dans les étapes précédentes (avec la condition suivante le nombre qui sert a diviser doit etre inférieur ou egale a la racine du nombre testé).
l'algorithme est très long et très couteux en temps de calcul.
On m'a dit que c'etait un mauvais algorithme et que l'on connaissait plus rapide... Pourriez vous m'indiquer une meilleur methode?
Je voudrais faire un algorithme pour extraire tous les nombres premiers inferieurs ou egaux a N.
Naivement, j'avais commencé par faire un algorithme récursif... c'est a dire
qu'il connaissait les nombres premiers suivant : {2,3,5}
puis il faisait une boucle qui pour chaque nombre essayait de diviser par chaque nombre premier déja connu dans les étapes précédentes (avec la condition suivante le nombre qui sert a diviser doit etre inférieur ou egale a la racine du nombre testé).
l'algorithme est très long et très couteux en temps de calcul.
On m'a dit que c'etait un mauvais algorithme et que l'on connaissait plus rapide... Pourriez vous m'indiquer une meilleur methode?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
La méthode du crible est très exactement celle qu'utilise Evariste Galois, il faut améliorer deux points : Ne pas prendre tous les entiers, mais par exemple, au dela de 3, seulement ceux de la forme 6n-1 ou 6n+1. et plutôt que la racine carrée, comparer le quotient avec le diviseur.
Par contre, la forme récursive est pratique pour concevoir un programme, mais il faut l'éviter dans l'écriture finale; il existe des techniques classiques de dérécursion, qui transforment une récursion en une simple boucle sans appels nombreux à la mémoire.
Cordialement
(c'est (sans doute?) moins stupide qu'il n'y parait, car la fonction est prévue pour dire simultanément, parmi une liste de nombre, lesquels sont premiers ; évidement pour une liste d'un seul nombre ça fait un peu bizarre...).
Gerard : la méthode utilisé par Eva est, formellement, le crible, mais tel qu'il l'a implantée, il fait des divisions et extrait des racines carrés au lieu de faire de simples additions.
Le mieux est d'avoir un algo "multiple" (Y a une denomination particuliere pour ce genre d'algo mais je ne m'en rappelle plus) qui en fonction de la taille de ton nombre adopte la meilleur technique.
Enfin, une derniere technique, la liste des 1000000 premiers nombres premiers est disponible sur le net, tu peux donc faire une recherche dans cette liste...
Cordialement,