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

Présentation
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.
Téléchargement
0  0 
Téléchargé 16 fois Voir le commentaire
Détails
Catégories : Mathématiques
Avatar de Adrien SUAU
Nouveau membre du Club
Voir tous les téléchargements de l'auteur
Licence : Autre
Date de mise en ligne : 18 août 2014




Avatar de koala01 koala01 - Expert éminent sénior https://www.developpez.com
le 18/08/2014 à 20:53
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
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
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
Developpez.com décline toute responsabilité quant à l'utilisation des différents éléments téléchargés.
Contacter le responsable de la rubrique C