IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Téléchargez C++ Discussion :

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


Sujet :

Téléchargez C++

  1. #1
    Invité
    Invité(e)
    Par défaut [C++11] Nombres premiers de 0 à N.
    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 ?

  2. #2
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    octobre 2004
    Messages
    11 488
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : octobre 2004
    Messages : 11 488
    Points : 29 806
    Points
    29 806
    Par défaut
    Salut,
    Citation Envoyé par Nelimee Voir le message
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

Discussions similaires

  1. Réponses: 24
    Dernier message: 27/09/2005, 21h16
  2. [défi n°8]: premiers nombres premiers
    Par javatwister dans le forum Général JavaScript
    Réponses: 41
    Dernier message: 14/06/2005, 10h22
  3. [LG]Calcul des 15 premiers nombres premiers
    Par yffick dans le forum Langage
    Réponses: 12
    Dernier message: 18/09/2004, 14h57
  4. Cripter avec des nombres premiers
    Par clovis dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 14/04/2004, 19h10
  5. premier nombre premier superieur à m=10^100+1
    Par azman0101 dans le forum Mathématiques
    Réponses: 4
    Dernier message: 17/04/2003, 03h23

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo