C++ calcul d'un nombre prmier

C++ calcul d'un nombre prmier - C++ - Programmation

Marsh Posté le 10-12-2018 à 09:21:09    

Bonjour,
je débute dans le C++ et on me demande de faire une fonction booléenne qui, à partir d'un entier en paramètre retourne 1 si il est premier ou 0 s'il ne l'est pas.
J'ai déjà épluché les forums ou internet mais je ne trouve pas ce qui me convient (la plupart des forums proposent la solution pour trouver tout les premiers de 1 à une limite, moi je ne veux que 1 seul nombre premier)

Reply

Marsh Posté le 10-12-2018 à 09:21:09   

Reply

Marsh Posté le 10-12-2018 à 10:07:17    

Soit n le nombre que t'intéresse, l'approche simple consiste à examiner le résultat de n modulo d.

 

Vu ta date de naissance j'imagine que tu dois débuter des études d'info, donc si t'es pas encore familier avec le concept : modulo renvoie le reste d'une division euclidienne, par exemple, 5 mod 2, renvoie 1, car 5/2 = 2 reste 1. Si tu trouves un reste nul, c'est que d est un diviseur de n, et donc que n n'est pas premier.

 

En bref, tu pars du principe que n est premier et défini donc un booléen sur true. Tu créés une boucle sur d, allant de 2 à la racine carrée de n (inutile d'aller plus loin, si ton nombre n'est pas premier, tu trouveras un diviseur dans l'intervalle allant de 2 à la racine de ce nombre incluse), et tu regardes le résultat de mod. Si à un moment ça te retourne 0, c'est que n n'est pas premier, du coup tu peux définir ton booléen sur false et sortir immédiatement de ta boucle. Si à la fin de ta boucle tu n'as jamais eu 0 comme résultat, ton booléen est déjà sur true, tu peux retourner le résultat.

Message cité 1 fois
Message édité par Erlum le 10-12-2018 à 10:08:18
Reply

Marsh Posté le 10-12-2018 à 11:03:22    

Erlum a écrit :

Soit n le nombre que t'intéresse, l'approche simple consiste à examiner le résultat de n modulo d.  
 
Vu ta date de naissance j'imagine que tu dois débuter des études d'info, donc si t'es pas encore familier avec le concept : modulo renvoie le reste d'une division euclidienne, par exemple, 5 mod 2, renvoie 1, car 5/2 = 2 reste 1. Si tu trouves un reste nul, c'est que d est un diviseur de n, et donc que n n'est pas premier.
 
En bref, tu pars du principe que n est premier et défini donc un booléen sur true. Tu créés une boucle sur d, allant de 2 à la racine carrée de n (inutile d'aller plus loin, si ton nombre n'est pas premier, tu trouveras un diviseur dans l'intervalle allant de 2 à la racine de ce nombre incluse), et tu regardes le résultat de mod. Si à un moment ça te retourne 0, c'est que n n'est pas premier, du coup tu peux définir ton booléen sur false et sortir immédiatement de ta boucle. Si à la fin de ta boucle tu n'as jamais eu 0 comme résultat, ton booléen est déjà sur true, tu peux retourner le résultat.


 
Merci de ta réponse, j'en suis arrivé à ça comme fonction :
 

Code :
  1. bool premier(int val)
  2. {
  3.     int i=2;
  4.     int nbdiviseur=1;
  5.     while(i<sqrt(val)&&nbdiviseur<2)
  6.     {
  7.        if(val%i==0)
  8.        {
  9.            nbdiviseur=nbdiviseur+1;
  10.        }
  11.        i++;
  12.     }
  13.     if(i>val/2)
  14.     {
  15.         return 1;
  16.     }
  17.     else
  18.      return 0;
  20. }


 
mais du coté de mon programme principal, les réponse qu'il me donne sont incorrect (1 n'est pas premier, quand à 13 lui est sensé l'être)
 

Code :
  1. int main()
  2. {
  3.     int val;
  4.     cout<<"entrez une valeur entiere ";
  5.     cin>>val;
  6.     cout<<endl;
  7.     if(premier(val)==1)
  8.     {
  9.         cout<<val<<" est un nombre premier"<<endl;
  10.     }
  11.     else
  12.     {
  13.         cout<<val<<" n'est pas un nombre premier"<<endl;
  14.     }
  15. }


Message édité par sulfuross le 10-12-2018 à 11:07:46
Reply

Marsh Posté le 10-12-2018 à 11:22:30    

Quel est l'intérêt de ton if(i>val/2) ? Et pourquoi vouloir mémoriser le nombre de diviseurs ? Le résultat est le même mais ton code devrait refléter ton intention.

 

Et attention à ta condition de sortie de boucle, tu dois aller jusqu'à la racine incluse. Par exemple, pour savoir que 25 n'est pas premier, tu es obligé d'aller jusqu'à sa racine, 5.

 
Code :
  1. bool premier(int val)
  2. {
  3.     bool premier=true;
  4.     int i=2;
  5.     while(i<=sqrt(val) && premier)
  6.     {
  7.        if(val%i==0)
  8.        {
  9.            premier=false;
  10.        }
  11.        i++;
  12.     }
  13.     return premier;
  14. }
 

Version avec boucle for, plus lisible à mon opinion.

 
Code :
  1. bool premier(int val)
  2. {
  3.     bool premier=true;
  4.     for (int i=2 ; i<=sqrt(val) && premier ; i++)
  5.        if(val%i==0)
  6.        {
  7.            premier=false;
  8.        }
  9.     }
  10.     return premier;
  11. }

Message cité 1 fois
Message édité par Erlum le 10-12-2018 à 11:23:02
Reply

Marsh Posté le 10-12-2018 à 11:34:22    

Erlum a écrit :

Quel est l'intérêt de ton if(i>val/2) ? Et pourquoi vouloir mémoriser le nombre de diviseurs ? Le résultat est le même mais ton code devrait refléter ton intention.
 
Et attention à ta condition de sortie de boucle, tu dois aller jusqu'à la racine incluse. Par exemple, pour savoir que 25 n'est pas premier, tu es obligé d'aller jusqu'à sa racine, 5.
 

Code :
  1. bool premier(int val)
  2. {
  3.     bool premier=true;
  4.     int i=2;
  5.     while(i<=sqrt(val) && premier)
  6.     {
  7.        if(val%i==0)
  8.        {
  9.            premier=false;
  10.        }
  11.        i++;
  12.     }
  13.     return premier;
  14. }


 
Version avec boucle for, plus lisible à mon opinion.
 

Code :
  1. bool premier(int val)
  2. {
  3.     bool premier=true;
  4.     for (int i=2 ; i<=sqrt(val) && premier ; i++)
  5.        if(val%i==0)
  6.        {
  7.            premier=false;
  8.        }
  9.     }
  10.     return premier;
  11. }



 
 
 
 
le if(i>val/2) venais d'un camarade qui avais fait ça, même si je n'en avais pas trop compris l'utilité..
 
avec tes modifications le programme fonctionne beaucoup mieux, même si 1 est toujours considéré comme premier
 
du coup j'ai juste rajouté un if avant la boucle.
 

Code :
  1. if(val==1)
  2.     {
  3.         return false;
  4.     }

Reply

Marsh Posté le 10-12-2018 à 11:42:37    

Je te conseille de limiter le nombre de return dans tes fonctions à 1, ça rend les choses un peu plus faciles à lire.
 
A ta place j'écrirais donc plutôt if(val==1) premier=false. La condition de ta boucle n'est plus vérifiée de ce fait, donc tu vas aller directement à la fin de la fonction. Le résultat est le même, c'est du pinaillage, mais quand tu feras des trucs un peu plus compliqués tu verras que c'est pas plus mal, même si un return en plein milieu d'une fonction semble plus simple.

Message cité 1 fois
Reply

Marsh Posté le 10-12-2018 à 11:45:34    

Bonjour,
 
Attention petite erreur de syntaxe, il manque une accolade ouvrante pour le "for" dans le dernier code.
Sinon moi je garderai un "while" ou au moins interrompre le "for" dès qu'on trouve que le nombre n'est pas premier. Mais un "for" s'utilise plus dans l'esprit d'aller jusqu'au bout.

Message cité 1 fois

---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.
Reply

Marsh Posté le 10-12-2018 à 11:46:10    

Erlum a écrit :

Je te conseille de limiter le nombre de return dans tes fonctions à 1, ça rend les choses un peu plus faciles à lire.
 
A ta place j'écrirais donc plutôt if(val==1) premier=false. La condition de ta boucle n'est plus vérifiée de ce fait, donc tu vas aller directement à la fin de la fonction. Le résultat est le même, c'est du pinaillage, mais quand tu feras des trucs un peu plus compliqués tu verras que c'est pas plus mal, même si un return en plein milieu d'une fonction semble plus simple.


 
Merci du conseil, j'essaierai d'y faire attention les prochaines fois.
 
la fonction donne donc  
 

Code :
  1. bool premier(int val)
  2. {
  3.     bool premier=true;
  4.     if(val==1)
  5.     {
  6.         premier=false;
  7.     }
  9.     for (int i=2 ; i<=sqrt(val) && premier ; i++)
  10.     {
  11.         if(val%i==0)
  12.         {
  13.             premier=false;
  14.         }
  15.     }
  16.     return premier;
  17. }


 
qui de mon coté fonctionne sans soucis, merci de ton aide !

Reply

Marsh Posté le 10-12-2018 à 12:02:59    

MaybeEijOrNot a écrit :

Bonjour,
 
Attention petite erreur de syntaxe, il manque une accolade ouvrante pour le "for" dans le dernier code.
Sinon moi je garderai un "while" ou au moins interrompre le "for" dès qu'on trouve que le nombre n'est pas premier. Mais un "for" s'utilise plus dans l'esprit d'aller jusqu'au bout.


 
C'est le cas !  :)  
 
Et je ne vois pas pourquoi un for devrait s'utiliser pour "aller jusqu'au bout", c'est une excellente manière de structurer ses boucles qui oblige à penser de suite aux conditions d'arrêt contrairement à un while.

Reply

Marsh Posté le 10-12-2018 à 12:08:23    

Rien n'est obligatoire, je dis juste que les boucles "for" sont destinées aux boucles dénombrables, lorsque tu es capable à l'avance de définir le nombre de boucles réalisé.
 
Et une boucle "while" force d'autant plus à réfléchir afin d'éviter une boucle infinie. Une boucle "for" tu ne prends pas de risque. Après tout ça est très subjectif.


---------------
C'est en écrivant n'importe quoi qu'on devient n'importe qui.
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed