Discussion :

[mavina]

Coucou,

oui en fait je ne factorise pas en facteurs de nombre premiers, je ne fais que lister tous les diviseurs.

Une autre approche serait de prendre le truc à l'envers : pour chaque nombre en dessous de n, si il ne fait pas partie de la liste des diviseurs que j'ai déja mémorisé, je l'ajoute et j'ajoute tous les diviseurs de ce nombre à la liste des diviseurs de n.
On voit là une recursivité se profiler, et ça n'est pas le fort de java.
à tester :

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
 
	public List<Integer> getDiviseurs2(int n)
	{
		List <Integer>result=new ArrayList<Integer>();
		for(int i=n-1;i>=1;i--)
		{
			if(i==1)
					return result;
			if(!result.contains(i))
			{
 
				if(n%i==0)
				{
					result.add(i);
					result.addAll(getDiviseurs2(i));
				}
			}
		}
		return result;
	}

Cordialement

Fred

[jobherzt]

en effet, je pense que c'est mieux, mais ca n'est pas la peine d'aller a l'envers :-). le probleme venait surtout de la condition d'arret. dans tous les cas, ton algo boucle jusqu'a n. outre le fait qu'on peut se contenter de n'aller que jusqu'a racine de n, en divisant ton nombre a chqaue fois que tu trouves un diviseur, tu reduis d'autant la limite de ta boucle ! si tu cherches a factoriser 770, par exemple, tu peux boucler jusqu'a [racine (770)] = 28, donc 28 iterations. mais si, des que tu rencontre le diviseur 2, tu divise et tu recommence tu feras donc :

1 iteration -> on trouve 2, on divise par 2 -> d'office tu n'as plus qu'a chercher des diviseurs que jusqu'a sqrt(385) ~ 20

tu repars de 3 vers 5 -> 2 iterations (voire une si tu enses a aller de 2 en 2) tu divises, et tu sais que tu n'as plus qu'a chercher les diviseurs < sqrt(77) ~ 9

tu repars de 6 vers 7 une iteration, tu divise et tu recherche jusqu'a racine (11)~4. tu fais 4 iteration, tu ne trouve rien, c'est que 11 est premier, tu as fini. soit environ 8 iterations au lieu de 28...
en fait, a chaque fois que tu effectue une division tu reduis d'autant la borne sup de ta boucle, et donc le nombre d'iteration au final. je ne connais pas le java, donc je donne un pseudo code :

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
25
26
27
28
 
resultat <- []
 
factorise(N, depart)
 
//on traite le cas de 2 a part pour pouvoir ensuite avancer par pas de 2
si depart == 2
  tant que 2 divise N
    resultat[] <- 2
    N=N/2
  fin tant que
  factorise(N,3) // on recurse
sinon
  i<-depart
  tant que i ne divise pas N et i <= sqrt(N)+1// on cherche un diviseur
    i<-i+2
  fin tant que
  //si on en a trouvé un
  si i <= sqrt(N)+1
    tant que i divise N // on divise autant de fois que possible
      resultat[] <- i
      N=N/i
    fin tant que
    factorise(N, i+2) // on recurse
  sinon // c'est que N est premier, il n'y a plus de diviseurs
    resultat[] <- N // notre N est donc le dernier diviseur de notre nb de depart
  fin si
fin fonction

voila, c'est ecrit a la va vite mais l'idee y est. des qu'on trouve un diviseur, on en profite pour reduire N au maximum, et on repart de la ou on s'etait arrete vu qu'on sait qu'il n'y a pas de diviseur plus petit. dans le pire des cas, on sera en O(sqrt(N)) si N est premier, mais si ses diviseurs ne sont pas trop grand la complexité chute assez vite. par exemple, si N=2^10, ton algo fera 1024 iteration, 512 en prenant la racine comme limite, le mien en fera 12. j'ai ecrit ca vite fait, donc a mon avis on devrait souvent se retrouver avec un1 comme dernier diviseur, mais il suffit de rajouter quelques tests.

[ramirami]

Salut a vous tous,
Je continue a bosser sur ce fameux problème. Voici le début de mon code JAVA. J'aurais besoin de votre aide pour l'améliorer

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
25
26
import java.util.Scanner; // program uses class Scanner
 
public class PrimeNumbers
{
   // main method begins execution of Java application
 
public static void main( String args[] )
 
   {  
int number;
 
   	  // create Scanner to obtain input from command window
      Scanner input = new Scanner( System.in );  	  
 
 
 
      System.out.print( "Please enter a positive integer greater than 2 or a -1 to quit.\n " ); // prompt 
      number = input.nextInt(); // read first number from user
 
 
     for ( int i = 1; i <= Math.sqrt(number); i++ ) 
         System.out.printf( "%d  ", i );
 
 
   	}
 }

[ramirami]

Salut. J'ai amélioré mon code. Maintenant je suis en mesure d'obtenir les facteurs de n'importe quel nombre. Par contre, mon programme ne valide pas si un nombre est premier ou non. J'aurais besoin de votre aide pour améliorer mon code.

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
25
26
27
28
29
30
31
32
33
34
35
36
public class PrimeNumbers
{
   // main method begins execution of Java application
 
   public static void main( String args[] )
 
   {  
 
      System.out.print( "This program will determine whether or not an integer is prime " );
      System.out.print( "\n\n" );
 
 
   	  int number;
 
   	  // create Scanner to obtain input from command window
      Scanner input = new Scanner( System.in );  	  
 
 
 
      System.out.print( "Please enter a positive integer greater than 2 or a -1 to quit.\n " ); // prompt 
      number = input.nextInt(); // read first number from user
 
 
 
      // for statement header includes initialization,  
      // loop-continuation condition and increment
 
      for ( int counter = 1; counter <= number; counter++ ) 
      if(number % counter ==0)
      System.out.printf( "%d  ", counter );
 
      System.out.println(); // output a newline
 
 
   	}
 }

[jobherzt]

tu peux simplement mettre un

Code :

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

1
2
 
int isPrime=1;

au debut de ton code, et ensuite si tu trouve un facteur tu met a 0 :

Code :

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

1
2
3
4
5
6
 
 if(number % counter ==0)
{
      System.out.printf( "%d  ", counter );
      isPrime=0;
}

et tu verifie a la fin :

Code :

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

1
2
3
4
5
 
if(isPrime == 1)
{
   System.out.print( "Il est premier\n " );
}

[miloux32]

Sérieusement, il suffit de taper "nombre premier java" sous google pour avoir des 100aines de codes sources...

[iohack]

Sérieusement, il suffit de taper "nombre premier java" sous google pour avoir des 100aines de codes sources...

Arrête tout de suite ces insinuations, tu vas te faire traiter d'agresseur !!

[ramirami]

Bonjour Miloux32,

Biensûr j'ai fait des recherches sur google, mais je n'ai pas trouvé un code
convenable. Jusqu'a présent personne ne m'a vraiment aider avec un code utile qui fait la job. Donc je continue mes efforts.

Je vous rappele que ca fait juste un mois que j'ai commence a apprendre JAVA.
Mais toute aide est fortement appréciée.

Merci

[jobherzt]

Jusqu'a présent personne ne m'a vraiment aider avec un code utile qui fait la job

ca fait plaisir.... tu ne crois pas que tu pousses un peu, la ??

[ramirami]

Salut jobherzt,

Je crois que mon problème est très facile a résoudre pour plusieurs parmi vous qui maîtrisent bien JAVA. Cependant comme tu peux le constacter. J'ai affiché mon bout de code et personne n'a pris la peine de l'améliorer et de le rendre fonctionnel.

Merci quand même pour vos suggestions

[jobherzt]

euh... et mon avant dernier message, c'etait quoi ? je t'ai mis texto le code java qui permet a ton programme de detecter aussi qu'un nombre est premier...

faut pas pousser meme dans les orties non plus... tu as eu plethore d'algorithme, des bouts de code, des codes complets, des conseils... a part te livrer une pizza on ne peut pas faire grand chose de plus...

[ramirami]

jobhertz. Je ne demande pas de me livrer une PIZZA. Je veux juste que quelqu'un rend mon code ci-dessous fonctionnel. Je ne comprends pas comment vous n'êtes pas capable de résoudre un petit problème . Ou bien pourquoi vous ne voulez pas m'aider.

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
25
26
27
import java.util.Scanner; // program uses class Scanner
 
public class PrimeNumbers
{
   // main method begins execution of Java application
 
public static void main( String args[] )
 
   {  
int iNumber;
 
   	  // create Scanner to obtain input from command window
      Scanner input = new Scanner( System.in );  	  
 
 
 
      System.out.print( "Please enter a positive integer greater than 2 or a -1 to quit.\n " ); // prompt 
      number = input.nextInt(); // read first number from user
 
 
    for ( int counter = 1; counter <= iNumber; counter++ ) 
            if (iNumber % counter == 0)                         
      System.out.printf( " %d ", counter );   
 
 
   	}
 }

[jobherzt]

euh.. pourquoi u nous redonne ton ancien code ? ton programme du 13/02/2007 à 05h12 etait mieux que celui la, a un detail pres, il faut que tu arrete ton compteur a sqrt(number), et que tu demarre a 2 au lieu de 1. pour ce qui est de tester si le nombre est premier je t'ai deja repondu.

[ramirami]

Salut Jonhetrz,

J'ai modifié mon compteur. Mais je ne sais comment intégrer les modifications que tu m'as suggérées dans mon code. Peux-tu modifier svp mon code.

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
25
26
27
import java.util.Scanner; // program uses class Scanner
 
public class PrimeNumbers
{
   // main method begins execution of Java application
 
public static void main( String args[] )
 
   {  
int iNumber;
 
   	  // create Scanner to obtain input from command window
      Scanner input = new Scanner( System.in );  	  
 
 
 
      System.out.print( "Please enter a positive integer greater than 2 or a -1 to quit.\n " ); // prompt 
      number = input.nextInt(); // read first number from user
 
 
    for ( int counter = 2; counter <= Math.Sqrt(iNumber); counter++ ) 
            if (iNumber % counter == 0)                         
      System.out.printf( " %d ", counter );   
 
 
   	}
 }

[jobherzt]

dsl ramirami, il faut que tu te debrouilles un peu :-) je detaille :

avant ta boucle, tu cree un entier isPrime que tu met a 1.

dans ta boucle, si tu trouve un diviseur, tu met isprime a 0. c'est logique, si tu trouve un diviseur, alors ton nombre n'est pas premier !

si a la fin de ta boucle isPrime vaut encore 1, c'est que tu n'as pas trouvé de diviseur, donc que le nombre est premier. relis ca a la lueur du code que je t'avais mis plus haut !!

accessoirement, ton nombre s'appelle tantot number, tantot inumber, fait gaffe !

[ramirami]

sérieux je ne sais pas toujours comment intégrer ton explication dans mon code .

Peux-tu faire un petit effort et modifier mon code. ça serait gentil de ta part.

[jobherzt]

je le fais, mais honnetement je ne te rend pas service... tu n'as vraiment pas fais le debut d'n effort.. et sache aussi que je n'ai jamais fait de java de toute ma vie, alors verifie qand meme :-)

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
import java.util.Scanner; // program uses class Scanner   
 
public class PrimeNumbers {
 
	// main method begins execution of Java application   
 
	public static void main( String args[] )  { 
 
		int iNumber; // create Scanner to obtain input from command window  
 
		Scanner input = new Scanner( System.in );
 
		System.out.print( "Please enter a positive integer greater than 2 or a -1 to quit.\n " ); // prompt
 
		number = input.nextInt(); // read first number from user
 
		int isPrime=1;
 
		for ( int counter = 2; counter <= Math.Sqrt(Number); counter++ ) 
 
		{
 
			if (Number % counter == 0) 
 
			{
 
				System.out.printf( " %d ", counter ); 
 
				isPrime=0;
 
			}
 
		} 
 
		if(isPrime == 1) System.out.print( "Le nombre est premier" ); 
 
 
 
	}
 
}

tu vois, c'etait quand meme pas compliqué...

[iohack]

Sur quoi bloque tu exactement ( désolé, flemme de reprende tout depuis le début ) ?
Si c'est sur un problème de performences/optimisation, ce sujet n'a rien à faire ici car ce n'est pas un problème java mais d'algorithmique.
Si tu n'arrives pas à transcrire un algo en java parce que tes connaissances dans ce langage sont limitées, alors là, nous sommes là pour t'aider. Mais t'aider ne veux pas dire réfléchir à l'algo à ta place et encore moins te pondre le code tout fait.

[iohack]

je le fais, mais honnetement je ne te rend pas service... tu n'as vraiment pas fais le debut d'n effort.. et sache aussi que je n'ai jamais fait de java de toute ma vie, alors verifie qand meme :-)

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
import java.util.Scanner; // program uses class Scanner   
 
public class PrimeNumbers {
 
	// main method begins execution of Java application   
 
	public static void main( String args[] )  { 
 
		int iNumber; // create Scanner to obtain input from command window  
 
		Scanner input = new Scanner( System.in );
 
		System.out.print( "Please enter a positive integer greater than 2 or a -1 to quit.\n " ); // prompt
 
		number = input.nextInt(); // read first number from user
 
		int isPrime=1;
 
		for ( int counter = 2; counter <= Math.Sqrt(Number); counter++ ) 
 
		{
 
			if (Number % counter == 0) 
 
			{
 
				System.out.printf( " %d ", counter ); 
 
				isPrime=0;
 
			}
 
		} 
 
		if(isPrime == 1) System.out.print( "Le nombre est premier" ); 
 
 
 
	}
 
}

tu vois, c'etait quand meme pas compliqué...

demande à ramirami la note/promo qu'il a eu histoire de savoir ce que tes connances vallent dans le milieu de ce monsieur...

[jobherzt]

helas, je pense qu'on n'en sortira pas... je pense qu'il ne maitrise ni l'algo ni sa conversion.. dans cette situtation je prefere lui donner les 3 lignes qui manque en esperant (on peut rever), qu'il y jettera un coup d'oeil pour comprendre...