Discussion :

[Invité]

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 ?

[koala01]

Salut,

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