Discussion :

[Phils46]

Bien le bonjour,
je suis débutant en C et cherche sans relache depuis un moment comment afficher les x(disons 100)premiers nombres premiers...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include<stdio.h>
 
 
int x,y;
 
main(void)
{
          for(x=1;x<100;x++)
          {
             for(y=2;y<=(x/2);y++)
             {
                 if(x%y==0) break;
                 else printf("%4d ",x); break;
             }
          }
          return (0);
}

pour l'instant j'ai ceci mais il fait que me sortir les nombres impair... alors il me faudrait svp un peu d'aide... merci d'avance...

[SaintAmand]

Bonjour,

Puisque tu es débutant, je pense qu'il peut être bien de te conseiller d'excécuter ton code à la main pour comprendre ce qui ne va pas.

Apparemment, tu utilises un algo directement issu de la définition d'un nombre premier a savoir qu'un entier positif est premier ssi il n'a pas de diviseur positif strict. Même si ce n'est pas rapide, cela suffit amplement pour construire une petite table de nombres premiers.
Ton optimisation y<=(x/2) dans la boucle for peut être améliorée. En effet, si un entier positif n'est pas premier, nécessairement il admet un diviseur strict inférieur ou égal à sa racine (pourquoi?). Donc tu peux remplacer par y<=sqrt(x) ou mieux y*y<=x (ca t'évite d'utiliser math.h et c'est plus rapide).
Ensuite appliquons ton programme à x=47. Il commence par tester la divisibilité par 2. 47 n'est pas pair, donc il conclut que 47 est premier. Et il fera de même pour tout les entiers impairs. Attention, si x%y == 0, effectivement tu peux conclure que x n'est pas premier, dans le cas contraire tu ne peux rien dire, sauf si y est le plus grand diviseur possible, c'est-à-dire compte tenu de l'optimisation que je t'ai proposée, si y est le plus grand entier inférieur ou égale à la racine carré de x, ie si (y+1)*(y+1)> x. Ainsi pour x=47, il te faudra poursuivre le test jusque 6 (7*7 = 49 > 47) pour conclure à sa primalité.
Voilà, tu n'a pas grand chose à corriger à ton code.

Sinon, pour t'amuser (quand tu auras vu les tableaux de tailles fixes) un algorithme dejà beaucoup plus performant et hyper connu et celui d'Eratosthene. Voila comment il se présente. Supposons que tu veuilles dresser la liste des nombres premiers jusqu'à 50.
Tu écris (fais-le) tous les entiers de 2 à 50 (attention 1 n'est pas premier). 2 est premier. Tu barres tous ses multiples stricts (4, 6 etc) qui sont évidemment composés. Ensuite tu prends le suivant non barré, c'est-à-dire 3, et tu barres tous ses multiples stricts (6,9 etc). Et ainsi de suite, tu prends à chaque fois le prochain entier non barré et tu barres tous ses multiples stricts. A la fin, les entiers non barrés, sont les nombres premiers que tu cherches.

Exercice: Justifier cet algorithme (niveau seconde)

Pour son implémentation tu peux utiliser un tableau int tab[49], où tab[i]=1 si l'entier i+2 est premier, 0 sinon.

Voilà, je ne veux pas t'en dire plus pour ne pas brider ta créativité :-)

Sinon, le prototype main(void) n'est pas recommandé. Si j'en crois la FAQ de fr.comp.lang.c (question 9.4), seul deux prototypes sont acceptables:
int main(void) et int main(int argc, char *argv[]).
Ensuite, attention, à la ligne printf.....; break, le break n'appartient pas au même bloc que le printf. Si tel était ton intention, il te faut encadrer ces deux instructions avec des accolades, dans le cas contraire, revient à la ligne pour placer ton break au même niveau que le if. Un code proprement indenté améliorera sa lisibilité donc facilitera la correction des erreurs.
Enfin, tu devrais déclarer tes variables x et y à l'intérieur de la fonction main.

En espérant avoir été clair malgré l'heure tardive,

--
SaintAmand, également débutant.

[Phils46]

merci beaucoup je m'en vais de ce pas essayer tout cela... je redonnerai des nouvelles des exercices donnés

[Phils46]

je n'arrive décidément pas... je comprend la faille mais arrive pas à la corriger... arg

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include<stdio.h>
 
 
main(void)
{
          int x,y;
          for(x=1;x<100;x++)
          {
             for(y=2;(y*y)<=x;y++)
             {
                 if(x%y==0) break;
                 if(x%y!=0) printf("%4d ",x); break;
             }
          }
          getchar();
          return (0);
}

[Lucky-94]

je comprend la faille mais arrive pas à la corriger... arg

Je suis débutant également et je ne comprend pas comment vous pouvez voir la faille.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include<stdio.h>
 
 
main(void)
{
          int x,y;
          for(x=1;x<100;x++)
          {
             for(y=2;(y*y)<=x;y++)
             {
                 if(x%y==0) break;
                 if(x%y!=0) printf("%4d ",x); break;
             }
          }
          getchar();
          return (0);
}

Peut-être, pourriez-vous éclairer ma lanterne en ajoutant des commentaires à votre code?

Pourquoi (par rapport à votre premier code avoir ajouté une fonction getchar()?
Avez-vous suivit les conseil de SaintAmand?
Votre code répond-il à la définition de: nombre premier? http://fr.wikipedia.org/wiki/Nombre_premier

[Trap D]

Pourrait-on réfléchir un peu ?

je suis débutant en C et cherche sans relache depuis un moment comment afficher les x(disons 100)premiers nombres premiers...

je veux afficher les 100 premiers nombres premiers :
Mon problème peut se résumer à cette boucle :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
pour i de 1 à 100 par pas de 1 faire 
   trouver le prochain nombre premier
   l'afficher
fin pour

Trouver le prochain nombre premier ???
Celà veut dire que lorsque j'ai trouvé un nombre le suivant est forcément plus grand
Il faut donc que je mémorise ce nombre, et que je continue la recherche à partir du suivant de ce nombre.
Du suivant ?? Non, car je sais que les nombres premiers ne sont pas pairs sauf 2. Dons je peux partir sans problème de 3 et aller de 2 en 2
On peut raisonnablement écrire ce bout de prog :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
variable n : entier 
variable x : entier
variable i : entier
debut
   n <- 3
   pour i de 1 à 100 par pas de 1 faire 
      x <- prochain_nombre_premier(n)
      afficher(x)
      n <- x + 2
   fin pour
fin

Maintenant il faut écrire la fonction prochain_nombre_premier :
Qu'est-ce-que j'ai exactement en entrée ? un nombre
Quel est le résultat recherché ? un nombre premier supérieur ou égal au nombre fourni
Je sais que je dois faire incrémenter les nombres recherchés de 2.
ma fonction peut s'écrire ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
fonction prochain_nombre_premier(Entier n) retour entier
debut
	tant que pas_premier(n) = vrai faire
		n <- n + 2
	fin tant que
	retourner n
fin

Il ne reste plus qu'à écrire la fonction pas_ premier

Un nombre est premier s'il ne possède que 2 diviseurs 1 et lui-même.
Maintenant, un peu comme on vient de le voir, il faut tester avec 2 puis les nombres impairs consécutifs.
Dois-je tester avec 2 ? Non, puisque dans mon algo je n'utilise que des nombres impairs.

Dois-je faire toutes les divisions ?
Sachant que a = bq+r, si j'augmente le diviseurs b, le quotient diminue, donc dès que q devient inférieur à b, je peux m'arréter.
D'autre part, si le reste de la division donne 0, alors le nombre b n'est pas premier et je peux m'arréter.
On peut écrire la fonction

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
fonction pas_premier(entier n) retour booleen
variable b : entier
variable q : entier
variable r : entier 
variable retour : booléen
début
	remarque : on initialise retour à vrai
	retour <- vrai
 
	remarque : intialisations cohérentes pour la condition de boucle
	q <- n
	r <- n
	b <- 3
 
	tant que b <= q et r <> 0 faire
		r <- n mod b 
		q <- n div b
		b <- b + 2;
	fin tant que
	si r = 0 alors
		retour <- faux
	fin si
	retourner retour
fin

Analyse de l'algo, on regarde les conditions de départ :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
		q <- n
		r <- n
		b <- 3
 
		tant que b <= q et r <> 0 faire

Que se passe-t-il avec 3 au départ de l'algo ?
q <- 3
r <- 3
b <- 3
tant que 3 <= 3 et 3 <> 0 faire
je passe ce test donc
r <- 3 mod 3 (soit 0)
q <- 3 div 3 (soit 1)
je sors de la boucle : tant que 3 <= 1 et 0 <> 0 faire (le test est faux)
si 0 =0 alors
je réussis le test
retour <- faux
donc je renvoie faux pour 3 ce qui est incorrect.

Mon algo est-il incorrect, oui puisque 3 ne passe pas, mais non car pour tous les nombres supérieurs à 3, donc dès 5 les résultats sont bons.
A toi de voir ce que tu veux faire.
Tu peux utiliser cet algo en précisant bien les conditions d'utilisation.

[SaintAmand]

je n'arrive décidément pas... je comprend la faille mais arrive pas à la corriger... arg

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include<stdio.h>
 
 
main(void)
{
          int x,y;
          for(x=1;x<100;x++)
          {
             for(y=2;(y*y)<=x;y++)
             {
                 if(x%y==0) break;
                 if(x%y!=0) printf("%4d ",x); break;
             }
          }
          getchar();
          return (0);
}

Bon, qu'est-ce que nous fait là Phils ? :-(
D'où sort le getchar ? Hop, tu le vires.
Le problème se situe à l'intérieur de ta boucle for(y=2.....). Si y divise x, on est d'accord, x n'est pas premier. Cependant si y ne divise pas x alors x est premier si (y+1)^2 > x (s'il y a avait un diviseur on l'aurait deja trouvé), sinon il est trop tôt pour conclure et il faut poursuivre les tests.

--
SaintAmand