Programme C ++ Prime Numbers

Je travaille sur un programme C ++ qui détermine et affiche les nombres premiers compris entre 3 et un entier ‘x’ saisi par l’utilisateur. Je suppose que j’ai besoin d’une double boucle nestede pour cela, une pour parcourir de 3 à x et l’autre pour vérifier si le nombre est premier. Je pense qu’il faut faire quelque chose comme aller de 2 à x-1? Je ne sais vraiment pas comment faire cela en termes de syntaxe. Merci pour toute aide! 🙂

EDIT: Voici ce que j’ai:

#include  #include  using std::cout; using std::endl; using std::cin; int main(){ int x; int i; int j; cout << "Please enter an integer 'x' greater than 3: " <> x; if (x <= 3){ cout << "Please enter new value 'x' greater than 3: " <> x; } for(int i=3; i<=x; i++){ for(j=2; j<i; j++){ if(i%j == 0) break; else if(i == j+1); cout << i << endl; } } return 0; } 

Et moi, lorsque je saisis 10 en tant que ‘x’, je reçois la sortie: 3 5 5 5 7 7 7 7 7 9

Quelqu’un peut-il me dire comment résoudre ce problème?

Si votre X est suffisamment petit, vous pouvez utiliser le tamis d’Eratosthène pour le faire plus efficacement. Ceci est idéal pour les cas “nombres premiers jusqu’à X” car il conserve une mémoire de nombres premiers précédemment rejetés. Pour ce faire, il conserve un ensemble d’indicateurs pour chaque numéro de candidat, tous initialement réglés sur true (sauf pour 1, bien sûr).

Ensuite, vous prenez la première valeur vraie (2), vous la générez en tant que prime, puis vous définissez les indicateurs pour tous les multiples de cette valeur sur false.

Alors continuez avec:

  • 3;
  • 5 (puisque 4 était un multiple de 2);
  • 7 (puisque 6 était un multiple de 2 et 3);
  • 11 (puisque 8 et 10 étaient des multiples de 2 et 9 était un multiple de 3);
  • 13 (puisque 12 était un multiple de 2);
  • 17 (puisque 14 et 16 étaient des multiples de 2 et 15 était un multiple de 3 et 5);
  • etc.

Le pseudo-code serait similaire à:

 def showPrimesUpTo (num): // create array of all true values array isPrime[2..num] = true // start with 2 and go until finished currNum = 2 while currNum <= num: // if prime, output it if isPrime[currNum]: output currNum // also flag all multiples as nonprime clearNum = currNum * 2 while clearNum <= num: isprime[clearNum] = false clearNum = clearNum + currNum // advance to next candidate currNum = currNum + 1 

Sinon, vous pouvez diviser en procès selon votre suggestion. L'idée de base est de vérifier chaque nombre de 2 à la racine carrée de votre numéro cible pour voir s'il s'agit d'un multiple. En pseudo-code, ce serait quelque chose comme:

 def isPrime (num): // val is the value to check for factor val = 2 // only need to check so far while val * val <= num: // check if an exact multiple if int (num / val) * val == num: return false // no, carry on val = val + 1 // if no factors found, it is a prime return true 

La raison pour laquelle vous n'avez besoin que de vérifier la racine carrée est parce que, si vous trouvez un facteur supérieur, vous avez déjà trouvé le facteur correspondant sous la racine carrée.

Par exemple, 3 x 17 est 51 . Si vous vérifiez les nombres de 2 à 50 pour voir si 51 est premier, vous en trouverez 3 premier, ce qui signifie que vous n'avez jamais besoin de vérifier 17 .

 int main (char argv) { int tempNum = atoi(argv); for (int i=3; i<=tempNum; i++) for (int j=2; j*j<=i; j++) { if (i % j == 0) break; else if (j+1 > sqrt(i)) { cout << i << " "; } } return 0; } 

Imprimer des nombres premiers de 1 à 100 En gros, mais modifié

Je trouve celui-ci assez rapide et efficace

  int main(){ for(int i=3; i<=X; i++) if(IsPrime(i)){ cout<