Se connecter / S'enregistrer
Votre question
Fermé

Nombres premiers [C++] Helppppp

Tags :
  • Programme
  • Programmation
Dernière réponse : dans Programmation
30 Octobre 2005 21:02:49

Salut tout le monde !

J'ai un gros problème ! J'essaye de faire un programme sur les nombres premiers en C++ mais j'y arrive pas :-(:-(

Je vos explique ce que je cherche à faire afin que vous puissiez m'aider svp !

Tout d'abord je veux créer une fonction booléenne qui test si le nombre est premier ou pas.
Ensuite dans ma fonction principale main je veux que l'utilisateur saisisse un entier (ex:20) et que ça appelle la fonction est que ça m'écrive la liste de tous les nombres premiers entre 0 et n (ex:si n=20, ça affiche 7, 11,13,17,19).

Je souhaite aussi essayer une variante de ce programme, c'est a dire que l'utilisateur entre un entier, et que le programme le decompose en facteurs premiers, et donc que le programme dise si c'est un nombre premier ou pas (ex: 30=2*3*5, donc 30 n'est pas premier)

Mais J'AI TROPS DE MALLLLLLLL :-(

Si quelqu'un pouvait avoir l'amabilité de m'ecrire un exemple de ce que ça donnerait en C++

MERCI D'AVANCE ;-)

Autres pages sur : nombres premiers helppppp

30 Octobre 2005 23:29:21

Pour le moment j'ai que ça ! Je sais c'est vraiment peu mais je débute ...

Please Help



#include<iostream>
using namespace std;


bool testPremier(int nb)
{

//la je sais pas

}



int main()
{
int nb;

cout << "Veuillez saisir un nombre entier : " << endl;
cin >> nb;

if (testPremier(nb))
cout << "Ce nombre est premier" << endl;
else
cout << "Ce nombre n'est pas premier" << endl;

31 Octobre 2005 00:08:54

Un nombre premier est un nombre qui ne se divise que par lui même ou par 1. Donc si tu divise le nombre donné par 2, que le reste de cette division N'EST PAS EGAL à 0, c'est un nombre premier.

NB: excepté 2, qui est le seul nombre pair, premier.
Contenus similaires
Pas de réponse à votre question ? Demandez !
31 Octobre 2005 11:42:01

alors j'ai réfléchi a ce que tu ma répondu, mais il y a un probleme, en effet tu prends par exemple 15, si tu fais 15/2 ca fait 7 et le reste est 1. Donc le reste n'est pas égal à 0, pourtant 15 n'est pas premier puisqu'il est divisible par 3.

Je pense que pour trouver si le nombre est premier ou pas, il faut dire que s'il y a un reste après l'avoir divisé par 2, ou par 3, ou par 5 ou par 7, il est premier.

Mais mon rpoblème est surtout dans le fait de traduire ça en C++ dans ma fonction "testPremier" et aussi de pouvoir afficher ses facteurs premiers.

Merci quand meme mdy ;-)
31 Octobre 2005 11:53:40

bon bah, tu prends ton nombre n
i, un compteur
divisible, un booleen (faux, par defaut)
pour i de 2 à n (n non compris)
si n modulo i = 0
alors c'est divisible (divisible= vrai)
fin si
fin pour

pour afficher ces facteurs premiers, sans les stocker
n ton nombre
i, un compteur
pour i de 2 à n (n non compris)
si n modulo i = 0
alors affiche i
et n= n/i
fin si
fin pour
le n restant est forcement indivisible donc on l'affiche

voilà, avec ces bouts tu dois pouvoir facilement arriver a tes fins

31 Octobre 2005 13:16:53

Bein déjà un nombre premiers (mis à part 2) ne peut être premier donc déjà tu peux éliminé tous les multiples de 2n avec n aléatoires. et pour les nombres restants tu peux éliminé également tous les nombres étant des multiples de 2n+1(nombres impairs) avec n aléatoires mais dans les deux n il faut exclure la possibilité n=0 sinon tu obtients soit 0 soit 1 qui ne sont pas premiers. Tiens vois ce que tu peux faire avec cela et tiens au courant le forum. Et pour la décomposition en facteur premier il faut que tu fasses une boucle de division en sachant que tu ne dois obtenir que des nombres premiers.

Les nombres aléatoires peuvent être généré à l'aide de srand().
31 Octobre 2005 13:29:45

De plus pour limiter n, tu calcules la racine carré du nombre en prenant le nombre entier inférieur, de cette façon tu as le nombre qu'il ne faut pas dépasser, ainsi cela te permet d'éviter la boucle infini du for car cela te donne ts les nombres à tester, un exemple illustrera mieu ce concept. 27, sa racine vaut environ 5.2 en arrondissant à l'entier inférieur on retiendra 5. Donc tu généres ts les n tels que 2n<5 et 2n+1<5 ainsi tu as peu de nombre à généré. Enfin tu vois quoi.

Et à mon avis tu peux très bien développé cela sans fonction bouléenne, néanmoins cela peut être un bonne entrainement pour un débutant
31 Octobre 2005 13:53:46

en C, avec des macros :
FALSE et TRUE, entiers
MAX_N, le nombre le plus grand qu'on va donner, entier
  1. int testpremier(int n)
  2. {
  3. assert(n > 0);
  4. int i;
  5. for(i = 0; i <= sqrt(n); i++)
  6. if ((n % i) == 0) return FALSE
  7. }
  8.  
  9. int tous_les_premiers(int n)
  10. {
  11. assert(n > 0);
  12. int i;
  13. int crible[MAX_N];
  14. for(i = 0; i < MAX_N; i++)
  15. crible[i] = TRUE; //on dechoche toutes les cases du tableau
  16. for(i = 2; i < (MAX_N/2); i++)
  17. {
  18. if crible[i] = FALSE continue; //si le nombre n'est pas premier (est coché) on passe au suivant
  19. int j;
  20. for(j = 2; j*i < MAX_N; j++) //on coche tous les multiples du nombre
  21. crible[i*j] = FALSE;
  22. printf("%d\n", i); //on affiche le nombre premier
  23. }
  24. }


En ocaml :
  1. let est_premier nombre =
  2. assert(nombre > 0);
  3. let rec test = function
  4. 1 -> true
  5. | i -> (nombre mod i = 0) && test (i-1) //si i est un diviseur alors le nombre est un premier, sinon on regarde si (i-1) est diviseur etc...
  6. in test (floor (sqrt float(nombre))
  7. in
  8.  
  9. let tous_les_premiers nombre =
  10. assert(nombre > 0);
  11. let crible = Array.make nombre true;
  12. Array.iteri
  13. (fun indice est_premier ->
  14. if est_premier then begin
  15. let multiples = ref indice in
  16. while (!multiples * indice) < nombre do
  17. multiples := !multiples + indice;
  18. crible[!multiples] <- false;
  19. done;
  20. print_int indice; print_newline();
  21. end
  22. )
  23. crible;
  24. in


Une autre version ocaml de tous_les_premiers est :
  1. let tous_les_premiers m =
  2. let rec crible l = function
  3. | n when n > m -> l
  4. | n ->
  5. let p = List.fold_left (fun a b -> (n mod b <> 0) && a) true l in
  6. crible (if p then n :: l else l) (n + 1) in
  7. List.iter (fun i -> print_int i; print_newline();) (crible [] 2);;
31 Octobre 2005 13:53:56

en C, avec des macros :
FALSE et TRUE, entiers
MAX_N, le nombre le plus grand qu'on va donner, entier
  1. int testpremier(int n)
  2. {
  3. assert(n > 0);
  4. int i;
  5. for(i = 0; i <= sqrt(n); i++)
  6. if ((n % i) == 0) return FALSE
  7. }
  8.  
  9. int tous_les_premiers(int n)
  10. {
  11. assert(n > 0);
  12. int i;
  13. int crible[MAX_N];
  14. for(i = 0; i < MAX_N; i++)
  15. crible[i] = TRUE; //on dechoche toutes les cases du tableau
  16. for(i = 2; i < (MAX_N/2); i++)
  17. {
  18. if crible[i] = FALSE continue; //si le nombre n'est pas premier (est coché) on passe au suivant
  19. int j;
  20. for(j = 2; j*i < MAX_N; j++) //on coche tous les multiples du nombre
  21. crible[i*j] = FALSE;
  22. printf("%d\n", i); //on affiche le nombre premier
  23. }
  24. }


En ocaml :
  1. let est_premier nombre =
  2. assert(nombre > 0);
  3. let rec test = function
  4. 1 -> true
  5. | i -> (nombre mod i = 0) && test (i-1) //si i est un diviseur alors le nombre est un premier, sinon on regarde si (i-1) est diviseur etc...
  6. in test (floor (sqrt float(nombre))
  7. in
  8.  
  9. let tous_les_premiers nombre =
  10. assert(nombre > 0);
  11. let crible = Array.make nombre true;
  12. Array.iteri
  13. (fun indice est_premier ->
  14. if est_premier then begin
  15. let multiples = ref indice in
  16. while (!multiples * indice) < nombre do
  17. multiples := !multiples + indice;
  18. crible[!multiples] <- false;
  19. done;
  20. print_int indice; print_newline();
  21. end
  22. )
  23. crible;
  24. in


Une autre version ocaml de tous_les_premiers est :
  1. let tous_les_premiers m =
  2. let rec crible l = function
  3. | n when n > m -> l
  4. | n ->
  5. let p = List.fold_left (fun a b -> (n mod b <> 0) && a) true l in
  6. crible (if p then n :: l else l) (n + 1) in
  7. List.iter (fun i -> print_int i; print_newline();) (crible [] 2);;
31 Octobre 2005 14:50:37

merci pour toutes ces réponses, meme si je n'y arrive toujours pas lol (oui je sais je suis nul mais chut :-P )

par contre bluedylc j'ai du mal à passer du C au C++ parce que je connais rien au C
31 Octobre 2005 17:31:14

... Bah tu n'as qu'à penser que c'est du C++, où est le problème ?
31 Octobre 2005 17:32:21

... Bah tu n'as qu'à penser que c'est du C++, où est le problème ?
1 Novembre 2005 11:43:31

ben d'apres mon logiciel, par exemple "assert (n>0)", ce n'est pas reconnu donc deja ca c'est fait.
Apres "crible" je sais meme pas ce que c'est lol
1 Novembre 2005 11:46:42

ben d'apres mon logiciel, par exemple "assert (n>0)", ce n'est pas reconnu donc deja ca c'est fait.
Apres "crible" je sais meme pas ce que c'est lol
1 Novembre 2005 11:46:53

ben d'apres mon logiciel, par exemple "assert (n>0)", ce n'est pas reconnu donc deja ca c'est fait.
Apres "crible" je sais meme pas ce que c'est lol
Tom's guide dans le monde
  • Allemagne
  • Italie
  • Irlande
  • Royaume Uni
  • Etats Unis
Suivre Tom's Guide
Inscrivez-vous à la Newsletter
  • ajouter à twitter
  • ajouter à facebook
  • ajouter un flux RSS