Nombre Composé

Ce sont tes mots, mais l'énoncé exact .. c'est quoi .. sortir les nombres premier de 1 à (nombre que l'utilisateur à encoder) ?

"sortir les nombres premier de 1 à"
Une décomposition en facteur premier c'est trouver tous les entiers premiers qui divisent le nombre. Il ne s'agit donc pas d'énumérer tous les nombres premiers.

Exemples : 12=2*2*3, 17=17, 30 = 2*3*5,...

Bonsoir KX,

Tu sait décoder toi .. perso, j'ai du mal ! .. Merci

Pour moi un "algorithme qui décompose un nombre en facteur premier" c'est très explicite, c'est de l'algèbre niveau terminale (je ne sais pas si tu en es là)

Il faut trouver la série de nombres premiers dont le produit donne l'entier cherché.

Si je reprends mes exemples :

12 se décompose en [2,2,3] car 12=2*2*3 avec 2 et 3 qui sont premiers.
17 se décompose en [17] car 17=17 avec 17 qui est premier.
30 se décompose en [2,3,5] car 30=2*3*5 avec 2,3 et 5 qui sont premiers.

Quelques propriétés :
La décomposition en nombre premier est unique (à l'ordre près)
Un même nombre premier peut être utilisé plusieurs fois dans une même décomposition.

Je pense que j'ai plus de mal avec le français "ui fournira la décomposition du nombre eb facteur premier" qu'avec l'algorithme.

Ça semble un peu compliqué tout ça, en particulier la partie "recommencer la boucle au début du tableau."
De quel tableau tu parles ? De plus il n'est pas nécessaire de recommencer au début.
Si tu as déjà testé que X n'était pas divisible par P, alors X/Q ne sera pas non plus divisible par P.

Je pensait au tableau de nombres premier entre 1 et nombre X.
Mais on est pas obligé de mémoriser ce tableau .. on peut le faire à la volée.

En Java ça donnerait ça :

// version O(n)
public static void decomposer(int n)
{		
	for (int d=2; d<=n; d++)
	{
		while (n%d==0)
		{
			System.out.println(d);
			n/=d;
		}
	}
}

//version O(sqrt(n)/2)
public static void decomposer(int n)
{	
	while (n%2==0)
	{
		System.out.println(2);
		n/=2;
	}
	
	for (int d=3, max=(int) Math.sqrt(n); d<=max; d+=2)
	{
		while (n%d==0)
		{
			System.out.println(d);
			n/=d;
			max=(int) Math.sqrt(n);
		}
	}
	
	if (n!=1)
		System.out.println(n);
}

Crotte, je ne sait pas t'envoyer de message perso.
t'es sûr System.out.println(2); ?

Non, j'ai supprimé l'option MP, mais au besoin j'ai laissé la discussion que j'ai créé l'autre jour et que tu peux continuer (même si ça n'a rien à voir)

Le System.out.println(2); est correct, puisque c'est uniquement sur la boucle while (n%2==0) où je traite tous les nombres pairs (ce qui permet de faire d+=2 dans le for, au lieu de d++)

- Les variables "k" et "dec" doivent être initialisée, sinon, on pourrait avoir des surprises de mauvais goût !

- Avec ce code "dec = k & " * " ", "dec est à chaque fois réinitialisé .. il faut faire "dec = dec + k & " * " " pour ajouter en fin de chaîne

- Je pense que tu n'as pas saisi le fonctionnement du problème. Regarde ce qu'à écrit KX ici : https://forums.commentcamarche.net/forum/affich-26723985-nombre-compose#7
Cela te permettra de comprendre comment procéder.

Je ne comprends pas trop les algorithmes écrits comme ça, mais il me semble qu'il y a un autre problème, c'est que nbre ne change jamais.

Or puisque l'on compte plusieurs fois le même diviseur, il ne faudrait pas voir à faire une boucle infinie en faisant toujours le même test :

2 divise 600, donc on recommence avec 2
2 divise 600, donc on recommence avec 2
2 divise 600, donc on recommence avec 2
2 divise 600, donc on recommence avec 2
etc.

En réalité il faudrait faire :

2 divise 600, donc on recommence avec 2 et 300
2 divise 300, donc on recommence avec 2 et 150
2 divise 150, donc on recommence avec 2 et 75
2 ne divise pas 75, donc on recommence avec 3 et 75
etc.

Bonjour KX, Gradi,

Je suis heureux de voir que l'on peut toujours compter sur ta vigilance.

Il y a tellement à faire que je n'ai pas vu cette variable 'nbre' qui ne varie pas.
Effectivement, KX a raison .. quand tu as défini que nbre modulo 2 = 0 il faut alors diviser n par ce nombre ! c'est impératif !

Merci KX.