Forum |  HardWare.fr | News | Articles | PC | Prix | S'identifier | S'inscrire | Shop Recherche
1883 connectés 

  FORUM HardWare.fr
  Programmation
  C++

  C++ calcul d'un nombre prmier

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

C++ calcul d'un nombre prmier

n°2325923
sulfuross
Posté le 10-12-2018 à 09:21:09  profilanswer
 

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)

mood
Publicité
Posté le 10-12-2018 à 09:21:09  profilanswer
 

n°2325927
Erlum
Posté le 10-12-2018 à 10:07:17  profilanswer
 

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
n°2325928
sulfuross
Posté le 10-12-2018 à 11:03:22  profilanswer
 

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;
  19. }


 
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
n°2325931
Erlum
Posté le 10-12-2018 à 11:22:30  profilanswer
 

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
n°2325933
sulfuross
Posté le 10-12-2018 à 11:34:22  profilanswer
 

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.     }

n°2325934
Erlum
Posté le 10-12-2018 à 11:42:37  profilanswer
 

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.

n°2325935
MaybeEijOr​Not
but someone at least
Posté le 10-12-2018 à 11:45:34  profilanswer
 

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 en écrivant n'importe quoi qu'on devient n'importe qui.
n°2325936
sulfuross
Posté le 10-12-2018 à 11:46:10  profilanswer
 

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.     }
  8.     for (int i=2 ; i<=sqrt(val) && premier ; i++)
  9.     {
  10.         if(val%i==0)
  11.         {
  12.             premier=false;
  13.         }
  14.     }
  15.     return premier;
  16. }


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

n°2325938
Erlum
Posté le 10-12-2018 à 12:02:59  profilanswer
 

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.

n°2325939
MaybeEijOr​Not
but someone at least
Posté le 10-12-2018 à 12:08:23  profilanswer
 

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.

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C++

  C++ calcul d'un nombre prmier

 

Sujets relatifs
Nombre limite de fichiers dans un répertoire ?[RESOLU]Excel calcul des jours de garde
Compte rendu DareBoost, calcul performance de mon site webcalcul de checksum (réglé)
Calcul durée entre 2 dates et heures[C#] Charger un combobox plus rapidement
Calcul points de plusieurs events et membresRécupération adresse IP de ma Passerelle en C
déchiffrer encodage de nombre réelsCode jeux du nombre aléatoire en python 3.6
Plus de sujets relatifs à : C++ calcul d'un nombre prmier


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR