Algorithme pour nombres premiers de 0 à 1000

Version imprimable

Bonsoir,
Je voudrais afficher les nombres premiers de 0 à 1000 mais mon algorithme n'est jamais le bon.

J'ai essayé de procéder de la manière la plus simple avec les quelques notions que j'ai (je n'ai commencé à rentrer dans ce domaine que la semaine dernière). Cependant, je me retrouve face à un mur. Ce que je souhaite, c'est afficher les nombres premiers après compilation et non pas afficher "le nombre est premier". J'ai essayé de faire une boucle qui répéterait la vérification du nombre (1^er ou pas) en utilisant les données : un nombre premier est divisible par 1 et lui même.

Mais voilà, après compilation, je n'ai pas les nombres premiers qui s'affichent.
Ce que j'aimerais savoir, c'est ce qui manque à mon algorithme. Si je dois encore faire continue et ajouter d'autres données pour que les nombres premiers s'affichent.

Mon algorithme est le suivant :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include "stdio.h" void main() { int=i ; i=0 while(i<1000) { i=i/i , i=i/1 ; if(i==0) { printf("le nombre n'est pas premier ") ; } else { printf("le nombre est premier %i\n",i) ; } i++ } }
Merci à vous !

05/12/2019, 22h33
Bayard
Bonsoir,
- soit vous les afficher au fil de l'eau dans la boucle for. Supprimer les lignes "Ce nombre est premier" et ce "nombre n'est pas premier". Un printf(" %d",i); devrait faire l'affaire. Remarquez que j'ai mis un espace pour séparer les nombres. Un printf("%d\n",i); permet d'avoir des sauts de lignes.
- Soit vous les écrivez dans un fichier (avec un caractère d'espacement, exemple: un espace).
05/12/2019, 22h45
edgarjacobs

Hello,

1) ce code ne compile pas
2) que va-t-il se passser ligne 8 quand i vaut 0 ?
3) et même si le programme démarre avec i=1, i ne dépassera jamais 2 dans le while !
06/12/2019, 04h48
HamkitS

De ce que j'ai retenu en cours le % permet d'afficher la réponse avec en plus le type de variable ( %i, %f...) d est-il donc un type de variable nommé diviseur ?
06/12/2019, 06h08
Bayard

%d permet d'afficher des nombres entier.

Comme l'a dit edgarjacobs

Citation:

ce code ne compile pas

.
Prenez en compte cette remarque s'il vous plaît.
06/12/2019, 06h56
HamkitS

D'accord merci, je vais tout revoir d'abord
06/12/2019, 13h11
Guesset

Avant de commencer

Bonjour,

Un nombre premier n'est pas un nombre qui se divise par 1 ou lui-même (tous les nombres sont ainsi sauf 0). Un nombre premier est un nombre qui ne se divise que par 1 et lui même. L'algorithme trivial consiste à s'assurer qu'il ne se divise pas par un autre nombre entre 2 et n-1. Une première amélioration consiste à ne le vérifier qu'entre 2 et la racine carrée de n (arrondi inférieur genre floor(sqrt(n)) ). Une deuxième amélioration (si n maxi n'est pas trop grand comme ici) consiste à conserver les nombres premiers déjà trouvés dans un tableau et ne diviser que par ces nombres (toujours jusqu'à la racine carrée de n).

L'algorithme déterminé, le codage peut commencer (ne pas hésiter à bien vérifier que chaque élément sollicité du langage est bien compris).

Bon courage

Des lignes floues

Bonjour,
Merci à tous pour votre aide. Je n'ai cependant toujours pas réussi à trouver la bonne méthode. Peut-être un souci d'ordre et de boucle. J'ai trouvé un algorithme qui marche en faisant des recherches et comme mon titre il y a des lignes floues, je ne les comprends pas. Le voici
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include<stdio.h> void main() { int nombre=1, compteur=0; int i,r,n=100; while(compteur<n){//les n premiers r=0;//pour compter le nombre de diviseurs nombre++; for (i=1 ; i<=nombre ; i++) { if ((nombre%i)==0) r++; } if(r==2)//Le nombre premier se divise sur 1 et sur lui meme { printf(" %d \n",nombre); //on incrémente le compteur compteur++; } }
Mes questions sont :
-pourquoi le nombre=1 ? Est-ce le diviseur ?
-quelle est l'utilité du compteur ? Compter tous les diviseurs du nombres ? Et pourquoi commence-t-il par zéro ? Pourtant on écrit aussi r=0 pour compter ces diviseurs. Ce r veut-il dire que le reste de la division est toujours nul quel que soit le diviseur ?
-puis j'ai bien compris qu'un nombre premier ne se divise que par 1 et lui même mais pourquoi écrit-on if(r==2) de quel 2 parle-t-on ?
À chaque fois que je vois une boucle avec if dedans il y a toujours if(...=0) et if(...==2) je ne mets jamais le ==2 car je ne comprends même pas ce que ça veut dire.
J'essaie encore de trouver un moyen plus simple mais j'ai toujours un problème de boucle.
Par exemple, il est dit que j'utilise une variable que je n'ai pas déclaré alors que je l'ai fait.

Bonjour

Citation:

Envoyé par HamkitS

Je n'ai cependant toujours pas réussi à trouver la bonne méthode. Peut-être un souci d'ordre et de boucle.

Non. un souci de conversion du français vers un algo. Quand on te dit qu'un nombre premier n'a que 2 diviseurs (1 et lui-même), ça veut dire qu'il n'en a pas d'autre. Donc si tu en trouves un autre, c'est qu'il n'est pas premier.
Donc suffit de tester tous les diviseurs entre "1" et "le nombre" et si tu en trouves un, tu peux arrêter

Ensuite dans un souci d'optimisation, puisque 2 est le seul nombre pair à être premier, ça veut dire
que tous les autres pairs ne sont pas premiers
qu'il est inutile de tester un diviseur pair

donc on peut monter les diviseurs de 2 en 2 sur les impairs pour éviter certains tests inutiles

Toujours dans un souci d'optimisation, si p divise n et donne q, ça veut dire que q divise n et donne p. Donc si en testant les diviseurs tu arrives sur un résultat plus petit que le diviseur testé tu peux arrêter.
Ainsi dans (par exemple) 37, tu testes 3 (résultat 12), 5 (résultat 7), 7 (résultat 5) et là tu t'arrêtes car tu ne trouveras aucun diviseur qui divise exactement 37 et donne un résultat plus petit (sinon tu l'aurais trouvé avant).

Donc un algorithme de base pour tester si un nombre est premier pourrait être
Code:

1 2 3 4 5 6 7 8 9 10 11 12 si nombre <= 3 alors # cas particuliers de 0, 1, 2 et 3 si nombre <= 1 alors return False # 0 et 1 pas premiers fin si return True # 2 et 3 premiers fin si d=3 faire en infini si (nombre % d) == 0 return False si (nombre / d) < d return True d = d+2 fin faire
Citation:

Envoyé par HamkitS

J'ai trouvé un algorithme qui marche en faisant des recherches et comme mon titre il y a des lignes floues, je ne les comprends pas. Le voici
-pourquoi le nombre=1 ? Est-ce le diviseur ?

Si cela avait été un diviseur, alors il aurait divisé. Est-ce quelque part tu vois écrit / nombre dans le code ? Faut aussi faire des efforts de logique quoi. C'est le nombre qu'on veut vérifier.

Citation:

Envoyé par HamkitS

-quelle est l'utilité du compteur ? Compter tous les diviseurs du nombres ?

Il compte le nombre de nombres premiers. Tu veux les nombres premiers entre 1 et 1000 mais peut-être que tu veux aussi savoir combien l y en a...

Citation:

Envoyé par HamkitS

Et pourquoi commence-t-il par zéro ?

Ben sais pas trop. Quand tu comptes, toi, tu commences à combien ? 8523 ??? Moi personnellement je commence à 0. Enfin en réalité je commence à 1 car naturellement je compte des trucs qui existent (donc je fais "un" en montrant du doigt le premier truc) mais implicitement mon comptage a quand-même commencé à 0.

Citation:

Envoyé par HamkitS

Pourtant on écrit aussi r=0 pour compter ces diviseurs. Ce r veut-il dire que le reste de la division est toujours nul quel que soit le diviseur ?

Exactement. Quel que soit le diviseur, le reste est toujours nul et il n'y a strictement aucun nombre premier :roll:

Citation:

Envoyé par HamkitS

-puis j'ai bien compris qu'un nombre premier ne se divise que par 1 et lui même mais pourquoi écrit-on if(r==2) de quel 2 parle-t-on ?

"j'ai bien compris" dit-il tout en posant la question qui montre qu'il n'a rien compris du tout. Combien un nombre premier a-t-il de diviseurs ??? :roll::roll:

Citation:

Envoyé par HamkitS

À chaque fois que je vois une boucle avec if dedans il y a toujours if(...=0) et if(...==2) je ne mets jamais le ==2 car je ne comprends même pas ce que ça veut dire.

Oui, moi non plus. Quand je vois une boucle avec des trucs dedans, je ne les mets pas car je me dis que ça ne doit pas trop servir à grand chose :roll::roll::roll:

Citation:

Envoyé par HamkitS

Par exemple, il est dit que j'utilise une variable que je n'ai pas déclaré alors que je l'ai fait.

Non. Si le compilateur te dit que tu ne l'as pas fait c'est que tu ne l'as pas fait.

09/12/2019, 09h40
emixam16

Franchement tu es complétement bloqué sur cet algorithme. Mon conseil dans ces cas là est de prendre du recul avec une feuille et un crayon.

Écris sur sur une feuille un algorithme en français pour trouver tes nombres premiers. Une fois écrit, déroule ton algorithme à la main pour te convaincre qu'il fonctionne. C'est important de le tester rigoureusement instruction par instruction et pas "en gros ça doit marcher" car c'est exactement le type de code qui ne marche pas.

Tu pourras traduire ton code en C uniquement quand ce travail sera fini. Si ton algorithme est juste, la traduction est simple et rapide.
--
J'aimerais ajouter que la programmation demande *énormément* de rigueur et a fortiori en C. La moindre petite erreur peut avoir des conséquences considérables (passer des heures à déboguer, créer des méchants bugs, créer des erreurs de segmentation...). Force toi à être rigoureux ou tu n'y arrivera jamais.

Bon courage.

J'ai repris ton code qui marchait (pour peu qu'on rajoute l'accolade manquante) puis renommé les variables et réduit leur portée.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include<stdio.h> void main() { int const compteMax = 100; //anciennement n int compteur = 0; //nombre de nombres premiers trouvés int nombreActuel=1; //anciennement nombre while(compteur<compteMax) //les n premiers { int nbDiviseurs=0; //anciennement r int diviseur; nombreActuel++; for (diviseur=1 ; diviseur<=nombreActuel ; diviseur++) { if ((nombreActuel%diviseur)==0) nbDiviseurs++; } if(nbDiviseurs==2)//Le nombre premier se divise sur 1 et sur lui meme { printf(" %d \n", nombreActuel); //on incrémente le compteur compteur++; } } }
N'est-ce pas plus compréhensible ainsi?

Après, ce code n'affiche pas les nombres premiers de zéro à 1000, mais les cent premiers nombres premiers. Mais c'est facile à corriger: Il te suffit de te débarrasser de compteur et compteMax et remplacer le while par une autre boucle pour faire évoluer nombreActuel de zéro à 1000...