Se connecter avec
S'enregistrer | Connectez-vous

Nombres premiers [C++] Helppppp

Dernière réponse : dans Programmation

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

Lassé par la pub ? Créez un compte

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;

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.

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 ;-)

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

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().

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

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);;

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);;
Lassé par la pub ? Créez un compte

Créer un nouveau sujet

Tom's guide dans le monde