nombres premiers

Question

Bonjour à tous, je suis actuellement étudiant en BTS IRIS, et j'ai un TD à faire, qui peut paraître assez simple mais dont je ne vois pas comment me sortir.

Je dois coder un petit programme qui demande à l'utilisateur de rentrer un nombre, et qui dit ensuite si ce nombre est un nombre premier, ou non...

J'ai donc pensé m'y prendre de la façon suivante:

main ()
{
    int nb, res, div, verif=  0;
    
    printf("Veuillez entrer un nombre entier: ");
    scanf("%d",&nb);
    for(div=2;div<=  Je ne vois pas quoi mettre ici  ,div++)
    {
        if(div   == nb)
         {
            continue;
         }
        res = nb % div
         if(res != 0)
        {
              printf("Votre nombre n'est pas un nombre premier");
              verif = 1
         }
    }
    if (verif == 0)
    {
       printf("Votre nombre est un nombre premier");
    }
    getch();
}

Ce code me semble bon, sauf qu'il faut définir un div variant de 2 à n or que mettre pour n ? On ne sait jamais jusqu'à combien diviser un nombre pour savoir s'il est premier ou non n'est-ce pas ? (Remarque je suis nul en maths.. donc il y a peut-être une méthode plus simple pour calculer un nombre premier mais je ne la connais pas...)

Et si j'utilise un do while, où l'arrêter ? Si je demande à ce qu'il s'arrête quand (nb % div) est différent de 0 et que ce nombre est un nombre premier, ça ne s'arrêtera jamais, le programme ne risque pas de bugger ? 

Merci d'avance pour vos éventuelles réponses.

BruNews · Answer

Limite à racine carrée du nombre.
Il y a des tas de sources sur les nombres premiers où quasi tout a déjà été dit en commentaires, il faut t'y référer, les sources sont là pour ça.

ciao...
BruNews, MVP VC++

acx01b · Answer

salut
#include<math.h>
int estpremier (int n) {
  int sqrt_n, i;
  if (!(n%2)) return 0;
  sqrt_n = sqrt(n);
  for (i = 3; i <= sqrt_n; i+=2) {
    if (!(n%i)) return 0;
  }
  return 1;
}

Nombres premiers

2 réponses

Votre réponse

Discussions similaires