[debutant] Algorithme nombres premiers!

**Javamar** · 29/01/2009, 14h22

Code :

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

1
2
3
4
5
6
7
8
9
class NombrePremier
{ static int d=2;
static void premier(n)
 { for(d=2;d<n; d++)
    {if(n%d==0) break;}
   if (n%d==0) System.out.println(n+"n'est pas premier")
   else System.out.println(n+"est premier")
 }
}

quand j'execute ce programme, 9 est premier!! ça me parait bizzare.quelqu'un pourrait-il m'expliquer pourquoi 9 apparait premier dans ce programme?

Et quand je fais break, je sors de la boucle avec quelle valeur de d, est c'est la valeur de d(static int d=2) ou la dernière valeur de d avant de sortir de la boucle.
merci d'avance

**millie** · 29/01/2009, 14h34

Salut,

Ton programme ne compile pas.
Pourquoi mets-tu d en static ? Pourquoi n'y a t'il pas de typage pour n ?

**nouknouk** · 29/01/2009, 14h39

et si on fait les petites corrections qui s'imposent, c'est l'inverse de ce que tu dis qui se produira: même les nombres premiers seront considérés comme 'pas premiers' (genre '5').

La raison est simple: lorsque tu sors de la boucle for, c'est que la condition (d<n) n'était plus remplie. En d'autres termes, c'est que d vaut la première valeur qui ne remplit plus la condition (à savoir la valeur 'n'), et ne vaut pas la dernière valeur pour laquelle la boucle a été exécutée (n-1).

Un algo qui fonctionne ressemblerait plutôt à :

Code :

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

1
2
3
4
5
6
7
8
9
public static void premier(int n) {
	for(d=2;d<n; d++) {
		if(n%d==0) { 
			System.out.println(n+"n'est pas premier ("+n+"/"+d+" = "+(n/d)+")");
			return;
		}
	}
	System.out.println(n+"est premier.");
}

PS: pour optimiser l'algo, tu peux itérer pour un 'd' valant entre 2 et racine carrée de 'n'. De même, tu peux d'emblée éliminer toutes les valeurs paires.

**Javamar** · 29/01/2009, 14h49

En fait un nombre premier n est un nombre dont les seuls diviseurs sont 1 et n.Mon programme consiste à sortir de la boucle dès qu'il y a un d(different de 0 et de 1) qui divise n.Supposons que n=9 et que je sors de la boucle avec la valeur d=3 car 3 divise 9.La question que je me pose est la suivante: est ce que la valeur de d va être 3 au contraire elle reste 2(à cause de static int d=2)?

**Javamar** · 29/01/2009, 14h51

si mon programme compile belle et bien, j'ai omis de mettre premier(int n)

**Astartee** · 29/01/2009, 14h54

Je crois qu'on a tous compris le principe de ton algorithme, même mal codé

Envoyé par Javamar

La question que je me pose est la suivante: est ce que la valeur de d va être 3 au contraire elle reste 2(à cause de static int d=2)?

"static" ne veut pas dire "final"... A la sortie de la boucle, d vaut bien 3.
Cependant, comme on te l'a expliqué plus haut, si on sort "normalement" de la boucle (c'est-à-dire sans passer par le break) c'est parce que d vaut n. Et donc le test qui suit renverra toujours vrai (n%n==0), et donc les nombres premiers ne seront pas reconnus.
De plus, tu n'as aucun besoin de déclarer une variable d statique si c'est pour l'utiliser de manière locale dans une boucle...

Une fonction qui marche :
EDIT : arf nan, nouknouk l'a déjà postée

**nouknouk** · 29/01/2009, 14h55

Envoyé par Javamar

En fait un nombre premier n est un nombre dont les seuls diviseurs sont 1 et n

Lol. tu m'en apprends dis-donc !

Mon programme consiste à sortir de la boucle dès qu'il y a un d(different de 0 et de 1) qui divise n.Supposons que n=9 et que je sors de la boucle avec la valeur d=3 car 3 divise 9.La question que je me pose est la suivante: est ce que la valeur de d va être 3 au contraire elle reste 2(à cause de static int d=2)?

Le static dit [EDIT: grilled par Astartee ; chacun son tour

]

Mais je réaffirme ce que j'ai dit ci-dessus: l'aglo tel que tu nous l'a présenté (et modulo les fautes de syntaxe) ne trouvera pas '9' comme nombre premier. Au contraire, aucun nombre qu'on lui donnera ne sera considéré comme premier.

si mon programme compile belle et bien, j'ai omis de mettre premier(int n)

Et quelques points-virgule également

**Javamar** · 29/01/2009, 15h29

Vous avez peut-être raison de dire que au sortir de la boucle d=n.En fait moi je ne pense pas la même la chose que vous.Moi je me dis que dès lors qu'il va exister un d qui est tel que n%d==0, on sort de la boucle(grâce au break), on ne continue plus à regarder d'autres d(à incrementer).C'est déja suffisant pour dire que n n'est pas premier parceque nous avons trouvé une autre valeur qui divise n autre que 1 et N

**Javamar** · 29/01/2009, 15h30

On arrive donc pas forcement à n-1

**nouknouk** · 29/01/2009, 15h38

Envoyé par Javamar

On arrive donc pas forcement à n-1

Quand on sort prématurément de la boucle, le fonctionnement est effectivement correct (le nombre ne sera pas premier).
Mais chaque fois qu'on sortira 'normalement' en fin de boucle (ie. chaque fois que 'n' est effectivement un nombre premier), tu sortiras de ta boucle avec d=n et donc ton nombre sera considéré comme non premier!

Pour le reste, au risque de me répéter:

Mais je réaffirme ce que j'ai dit ci-dessus: l'aglo tel que tu nous l'a présenté (et modulo les fautes de syntaxe) ne trouvera pas '9' comme nombre premier. Au contraire, aucun nombre qu'on lui donnera ne sera considéré comme premier.

Donc soit l'algo que tu nous a écris en premier post n'est pas celui que tu exécutes, soit tu t'es planté dans l'explication de ton problème ("quand j'execute ce programme, 9 est premier!!")

**dinobogan** · 29/01/2009, 15h39

Envoyé par Javamar

On arrive donc pas forcement à n-1

On ne parle pas de la sortie de boucle mais du test après la boucle : il n'est pas suffisant.

**Javamar** · 29/01/2009, 15h40

Ok merci je vais voir ça tout à l'heure.A ce soir

**adiGuba** · 29/01/2009, 15h42

Salut,

Ton code ne compiles pas et est super-mal indenté ! Est-ce si dur de faire un copier/coller correct ??? C'est franchement illisible (et j'espère que ce n'est pas comme cela dans ton vrai code).

Sinon j'aurais la même remarque que millie :

Envoyé par millie

Pourquoi mets-tu d en static ?

Pour moi d est une simple variable locale, et n'a vraiment rien à faire en static

a++

**Javamar** · 30/01/2009, 19h36

Salut à tous! merci de votre apport.Effectivement mon code n'est pas bon.Grâce à vous j'ai compris pleins de choses.J'ai essayé de faire mieux.Ca compile mais ça ne s'execute pas.Dans ce code je m'interesse beaucoup plus au nombre impaire.Les nombres paires on sait qu'ils ne sont pas premiers (sauf 2).
(le code donné par nouknouk marche bien)

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
class NombrePremier
{
      boolean estPremier =(n%2==0);
 
       static void premier(n)
    {  
        for(i=3;i<n; i=i+2)
           {if( estPremier) break;
 boolean estPremier=(n%i==0);
           }
 
if(estPremier)System.out.println(n+"n'est pas premier");
else System.out.println(n+"est premier");
   }
}

ce code compile bien.Mais à l'execution, quand n=1? CA MARCHE
N=2 ca marche aussi, n=3 ok, n=4 ok, mais ça ne marche pas pour n=5 en ce sens que lors de l'execution quand je donne à n la valeur 5, je change de ligne sans aucun resultat, tout bloque en fait.c'est à dire un truc du genre:

Donnez un entier positif:
5 (ce que je mets )
- (le trait represente ce que j'ai à la fin) et je ne peux plus bouger

**millie** · 30/01/2009, 19h37

Mais t'es sûr que c'est du Java ?
Ce code ne compile pas.

**Javamar** · 31/01/2009, 14h03

oui c'est bien du java!!

**adiGuba** · 31/01/2009, 14h21

Envoyé par Javamar

oui c'est bien du java!!

Envoyé par Javamar

ce code compile bien.

Pourtant mon compilateur ne veut pas compiler ton code :

Code :

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

1
2
3
4
NombrePremier.java:5: <identifier> expected
static void premier(n)
                     ^
1 error

Donc il faudrait qu'on essaye de corriger puis débugger un code qui ne correspond pas au code que tu compiles

C'est si dur que cela de faire un copier/coller ?

a++

**Javamar** · 01/02/2009, 13h30

voici les corrections.En fait je n'avais pas mis tout ce que j'ai sur mon ordi.

class NombrePremier
{

public static void premier(int n)
{ boolean pasPremier =(n%2==0);
for(i=3;i<n; i=i+2)
{if( pasPremier) break;
boolean pasPremier=(n%i==0);
}

if(pasPremier)System.out.println(n+" n'est pas premier");
else System.out.println(n+" est premier");
}
}

**Javamar** · 01/02/2009, 13h41

Encore une petite erreur

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class NombrePremier
{
 
public static void premier(int n)
{ boolean pasPremier =(n%2==0);
for(i=3;i<n; i=i+2)
{if( pasPremier) break;
 pasPremier=(n%i==0);
}
 
if(pasPremier)System.out.println(n+" n'est pas premier");
else System.out.println(n+" est premier");
}
}

Javamar est actuellement connecté Signaler un message hors-charte Envoyer un message privé Modifier/Supprimer le message