[C++11] Nombres premiers de 0 à N.

Salut,

Citation:

Envoyé par Nelimee

Bonjour,

Je vous propose un nouvel élément à utiliser : [C++11] Nombres premiers de 0 à N.

Points positifs:

Recherche d'un diviseur de N jusqu'à racine(N).
Les diviseurs ne sont cherchés que parmi les nombres premiers inférieurs à racine(N).

Point négatif:

Il faut calculer les nombres premiers de 2 à sqrt(N+1) pour tester la primalité de N+1.

Qu'en pensez-vous ?

trois choses...

D'abord, tu pourrais éviter bien des itérations si tu supprimais d'office la vérification pour les nombres pairs. Un petit
Code:

1 2 3 if(number% 2 == 0 && number!=0){ return false; }
avant même de calculer la racine carrée pourrait te faire gagner pas mal en performances ;)

Ensuite, je suis allergique à l'instruction break lorsqu'on ne se trouve pas dans un test à choix multiple (switch...case). Si i est plus grand que la racine carrée du nombre testé, et que tu arrives à atteindre i, c'est qu'aucun des nombres de primes n'est diviseur du nombre recherché. Autant renvoyer directement true, vu que l'on a alors la certitude que nous avons un nombre premier ;)

En outre, vu que tu transmet de toutes manières le tableau des nombres entiers qui ont déjà été calculés, pourquoi ne pas permettre à la fonction isPrime de rajouter le valeurs qu'elle a identifiées comme étant des nombres premiers :question: Transmet le tableau sous la forme d'une référence au lieu d'une référence constante, et isPrime pourra faire tout le boulot ;)

Enfin, si l'idée est de dresser la liste des nombres premiers, il est possible d'obtenir un résultat bien plus rapide en dressant la liste des valeurs comprises dans l'intervalle requis et en invalidant celles qui ne sont décidément pas des nombres premiers sous une forme proche de :
Code:

1 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 /** remplis le tableau donné en paramètre avec TOUTES les valeurs comprise dans l'intervalle donné */ void fillValues(std::vector<int> & toFill, int limit){ // évite que le tableau ne doive être redimentioné trop souvent toFill.reserve(limit+1); /*faisons simple, chaque nombre prend la position qui correspond à sa valeur dans le tableau */ for(int i = 0;i<=limit;++i){ toFill.push_back(i); } } /** invalide les multiples d'une valeur donnée */ void invalidateNonPrimes(std::vector<int> & toCheck, int value){ int multiplier = 2; while(value * multiplier <= toCheck.size()){ toCheck[value * multiplier] = 0; ++multiplier; } } void checkForPrimes(std::vector<int> & toCheck){ for(auto value : toCheck){ // il ne sert à rien ni de tester 1, ni de tester 0, ni les valeurs invalidées if(value <1) invalidateNonPrimes(toCheck, value); } } int main(){ std::cout << "Jusqu'à quel entier N voulez-vous calculer les nombres premiers? "; long long limit{0}; std::cin >> limit; // le tableau des valeurs std::vector<int> values; // on le remplit fillValues(values, limit); // on invalide les valeurs qui ne sont pas des nombres premiers checkForPrimes(values); // on supprime les valeurs invalides values.erase(std::remove_if(values.begin(),values.end(),[](int i){return i == 0;})); /* for(auto it : value){ std::cout<<it<< "est un nombre premier\n"; } */ return 0; }
Code non testé car pas de compilateur pour l'instant, mais il devrait être à peu près correct, aux erreurs d'attention près ;)