begin process at 2010 03 21 23:43:11
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > DÉCOMPOSITION D'UN NOMBRE EN PUISSANCE DE FACTEURS PREMIERS

DÉCOMPOSITION D'UN NOMBRE EN PUISSANCE DE FACTEURS PREMIERS


 Information sur la source

Note :
Aucune note
Catégorie :Maths & Algorithmes Classé sous :premier, decomposition Niveau :Débutant Date de création :14/11/2006 Date de mise à jour :18/11/2006 17:24:12 Vu :3 195
Auteur : riton91

Ecrire un message privé
Commentaire sur cette source (14)
Ajouter un commentaire et/ou une note

 Description

Enregistre dans une chaîne de caractère la décomposition d'un nombre en paramètres en facteurs premiers.
le code est accompagne de deux fonctions qui ont leur equivalent dans string.h:
addchaine() -> strcat()
longeurChaine() -> strlen()
(il est fort possible que vous les connaissiez)
isPrime() verifie si le nombre est premier.

Source

  • #include <math.h> //pour sqrt()
  • #include <stdio.h>
  • #include <stdlib.h>
  • //Calcule le nombre de caractère d'une chaîne
  • long longueurChaine(const char* chaine)
  • {
  • const char *c = chaine;
  • while(*c) c++;
  • return (c - chaine);
  • }
  • //Ajoute une chaîne à la suite d'une autre
  • void addchaine(char* dest, const char* source)
  • {
  • while(*dest) dest++;
  • while(*dest = *source)
  • {
  • dest++;
  • source++;
  • }
  • }
  • //Vérifie si le nombre est premier, renvoie 1 si vrai et 0 si faux
  • int isPrime(long nombre)
  • {
  • if(nombre==1 || nombre==0)
  • return 0;
  • long i;
  • //Verifie si le nombre a un diviseur autre que 1 et lui-même
  • for(i = 2 ; i <= sqrt(nombre) ; i++)
  • {
  • if (nombre % i == 0)
  • return 0;
  • }
  • return 1;
  • }
  • //Cherche la décomposition du nombre en puissance de facteurs premiers
  • int factPrime(long nombre, char* chaine)
  • {
  • int k;
  • //Efface la chaine
  • for(k = 0 ; k < 100 ; k++)
  • chaine[k]=0;
  • char chainetmp[100]={'/0'};
  • //Si le nombre est égale a 0, 1 ou est premier
  • //il n'a pas de décomposition
  • if (nombre == 0 || nombre == 1 || isPrime(nombre))
  • sprintf(chaine,"%d", nombre) ;
  • //Sinon
  • else
  • {
  • long i;
  • for(i = 2 ; i <= sqrt((double)nombre) ; i = i + 2)
  • {
  • int j = 0 ;
  • //Calcule la puissance du diviseur en cour
  • while (nombre % i == 0)
  • {
  • nombre /= i ;
  • j++ ;
  • }
  • //Affiche le diviseur avec sa puissance
  • if (nombre != 1)
  • {
  • if (j > 0)
  • {
  • if (j != 1)
  • sprintf(chainetmp,"%ld^%d * ", i, j) ;
  • if (j == 1)
  • sprintf(chainetmp,"%ld * ", i) ;
  • }
  • }
  • else
  • //Affiche le dernier diviseur avec sa puissance (si different de 1)
  • sprintf(chainetmp,"%ld^%d", i, j) ;
  • if (i == 2)
  • i--;
  • if(j > 0)
  • addchaine(chaine,chainetmp);
  • int k;
  • for(k = 0 ; k < 100 ; k++)
  • chainetmp[k]=0;
  • }
  • //Affiche le dernier diviseur (si different de 1)
  • if (nombre != 1)
  • {
  • sprintf(chainetmp,"%ld", nombre);
  • addchaine(chaine,chainetmp);
  • }
  • }
  • return 1;
  • }
  • int main()
  • {
  • long nb;
  • char chaine[100]={0};
  • printf("Entrez un nombre : ");
  • scanf("%Ld",&nb);
  • factPrime(nb,chaine);
  • printf("%s\n",chaine);
  • system("PAUSE");
  • } 
#include <math.h>   //pour sqrt()
#include <stdio.h>
#include <stdlib.h>

//Calcule le nombre de caractère d'une chaîne
long longueurChaine(const char* chaine) 
{
  const char *c = chaine;
  while(*c) c++;
  return (c - chaine);
}

//Ajoute une chaîne à la suite d'une autre
void addchaine(char* dest, const char* source)
{
  while(*dest) dest++;
  while(*dest = *source)
  {
      dest++;
      source++;
  }
}

//Vérifie si le nombre est premier, renvoie 1 si vrai et 0 si faux
int isPrime(long nombre)
{
	if(nombre==1 || nombre==0)
		return 0;
		long i;
	//Verifie si le nombre a un diviseur autre que 1 et lui-même
	for(i = 2 ; i <= sqrt(nombre) ; i++)
	{
		if (nombre % i == 0)
			return 0;
	}
	return 1;
}

//Cherche la décomposition du nombre en puissance de facteurs premiers
int factPrime(long nombre, char* chaine)
{
	int k;
	//Efface la chaine
	for(k = 0 ; k < 100 ; k++)
				chaine[k]=0;
	char chainetmp[100]={'/0'};
	//Si le nombre est égale a 0, 1 ou est premier
	//il n'a pas de décomposition
	if (nombre == 0 || nombre == 1 || isPrime(nombre))
		sprintf(chaine,"%d", nombre) ;
	//Sinon
	else
	{
		long i;
		for(i = 2 ; i <= sqrt((double)nombre) ; i = i + 2)
		{
			int j = 0 ;
			//Calcule la puissance du diviseur en cour
			while (nombre % i == 0)
			{
				nombre /= i ;
				j++ ;
			}
			//Affiche le diviseur avec sa puissance
			if (nombre != 1)
			{
				if (j > 0)
				{
					if (j != 1)
						sprintf(chainetmp,"%ld^%d * ", i, j) ;
					if (j == 1)
						sprintf(chainetmp,"%ld * ", i) ;
				}
			}
			else
				//Affiche le dernier diviseur avec sa puissance (si different de 1)
				sprintf(chainetmp,"%ld^%d", i, j) ;

			if (i == 2)
					i--;
			if(j > 0)
				addchaine(chaine,chainetmp);
				int k;
			for(k = 0 ; k < 100 ; k++)
				chainetmp[k]=0;
		}
		//Affiche le dernier diviseur (si different de 1)
		if (nombre != 1)
		{
			sprintf(chainetmp,"%ld", nombre);
			addchaine(chaine,chainetmp);
		}
	}
	return 1;
}
 int main()
 {
     long nb;
     char chaine[100]={0};
     printf("Entrez un nombre : ");
     scanf("%Ld",&nb);
     factPrime(nb,chaine);
     printf("%s\n",chaine);
     system("PAUSE");
 }

 Conclusion

c'est ma premiere source


 Historique

14 novembre 2006 23:04:49 :
menu en+
18 novembre 2006 17:24:12 :
j'ai fais l'amelioration des fonction qui manipulent les chaine

 Sources du même auteur

Source avec Zip EDITER UN FICHIER BIT PAR BIT
Toutes les sources de riton91

 Sources de la même categorie

Source avec Zip TRANSFORMER UN ENTIER EN DEUX NOMBRES COMPOSÉ DES MEMES CHIF... par thebroyeur
CALCULE LOG(X) par tagtog
Source avec Zip Source avec une capture ALGORITHME DE TRI D'UN TABLEAU PAR ORDRE CROISSANT OU DÉCROI... par Thuzhen
Source avec une capture CALCUL DE VARIANCE par Minilogus
Source avec une capture GÉNÉRATEUR DE CLÉS SUR 26 DIGITS AU FORMAT HEXADÉCIMAL par besilent
Toutes les sources de la catégorie Maths & Algorithmes

 Sources en rapport avec celle ci

Source avec une capture FACTORISATION D'UN ENTIER EN PRODUIT DE NOMBRES PREMIERS AVE... par darkor
Source avec Zip FACTORISATION D'UN NOMBRE EN NOMBRE PREMIER par Tearsofdestiny
Source avec une capture FACTORISATION D'UN NOMBRE par Faibbus
Source avec Zip GÉNÉRATION DE NOMBRES PREMIERS ET STOCKAGE DANS UN FICHIER par visdev
Source avec Zip DÉCOMPOSITION EN FACTEURS PREMIERS par Math_Ador

Commentaires et avis

Commentaire de BruNews le 14/11/2006 23:29:00 administrateur CS

Aucun besoin d'itérateur pour avoir la longueur:
long longueurChaine(const char* chaine)
{
  const char *c = chaine;
  while(*c) c++;
  return (c - chaine);
}

Ici même principe.
Il ne faut surtout pas faire d'appel de fonction pour un truc aussi trivial, c'est la ruine des performances.
void addchaine(char* dest, const char* source)
{
  while(*dest) dest++;
  while(*dest = *source) {dest++; source++;}
}

Quand on recode ce qui existe, on se doit de faire au moins aussi bien que l'existant et de préférence mieux.

Bonne continuation.

Commentaire de Joky le 15/11/2006 10:59:29

Et un long pour une longueur de chaîne c'est pousser le bouchon un peu loin :D

Commentaire de luhtor le 15/11/2006 16:06:52

Ca fait long comme programme juste pour décomposer un nombre.

Commentaire de Joky le 15/11/2006 16:09:39

En faite tout est long

Commentaire de Kirua le 15/11/2006 16:52:05

long et int c'est pareil Joky. Ce qui est différent, c'est long long.

En réalité, int et long sont des synonymes pour long int, et long long est un synonyme de long long int.

Commentaire de Joky le 15/11/2006 17:22:02

Ah ouai...
Etrange:)

Commentaire de Kirua le 15/11/2006 17:50:18

J'ai trouvé ça aussi ^^.

Sinon, pour l'algo en soi, j'ai une proposition.

Tu vérifies un grand nombre de fois si un tel nombre est premier. Heureusement, tu ne vérifies chaque nombre qu'une seule fois, mais ce serait sans doute plus efficace de générer la liste des nombres premiers de 2 à n pour un certain n pas trop grand (là, ça dépend de ce que tu veux factoriser: des nombres de quel ordre de grandeur?), ce qui se fait très très vite avec un crible d'Eratosthène pas trop mal écrit, ce qui te permettra de déjà pas mal réduire le nombre à factoriser en peu d'opérations. Si, pas de chance, le nombre comporte un facteur premier plus grand que n, tu peux te rabattre sur ton autre technique, mais tu sauras au moins que les facteurs restants sont de toute manière supérieurs à n.

Dans le pire cas, il ne reste qu'un facteur (le nombre est premier quoi ^^), et t'as pas de bol. Mais tu peux parfaitement effectuer ce test au début de ta fonction.

Dans le cas ou il n'est pas premier, tu sais qu'il y a au moins deux facteurs premiers supérieurs à n. Pour faire simple, ça veut dire que le nomre que tu dois factoriser vaut AU MOINS (n+1)².

En soi, ça n'est pas intéressant, mais tu peux en tirer une façon simple de déterminer le n qui sera le plus adapté pour toi. Imaginons que tu veuilles couvrir tous les entiers positifs représentables par un unsigned long int, on a que tu dois générer les nombres premiers jusque sqrt(2^32-1) - 1 ~= 65535.

C'est un résultat intéressant: générer les nombres premiers de 2 à 65535, ça prend quasi rien comme temps, et tu ne dois le faire qu'une fois au démarrage du programme.

En conclusion, on aurait ça:

decomposer(m)
{
si m est premier
retourner m
sinon
pour chaque nombre l dans L
si l divise m
ajouter l à la liste des facteurs
m = m / l
recommencer le test pour ce l-ci
fin
fin
fin
}

pour le "recommencer le test pour ce l-ci", le plus clair c'est d'utiliser une boucle while et de n'incrémenter le compteur que si le test "si l divise m" a échoué.

Bon, j'ai pondu ça à l'instant, c'est sans doute pas optimal, mais c'est un résultat intéressant quand même :).

PS: en réalité, tu n'as même pas besoin de tester la primalité de m au démarrage de l'algo: s'il est premier, on est certain qu'aucun facteur dans L ne le divisera -> avant de retourner la liste des facteurs, vérifie que la liste est non vide. Si elle l'est, met m dedans: ça fera l'affaire, et tu n'auras pas à coder de fonction isPrime (qui était le point faible de cette version ^^).

j'espère que j'étais environ clair: hésite pas à poser des questions.

Commentaire de Kirua le 15/11/2006 17:56:10

Arf, désolé, j'ai oublié une ligne: celle qui définit L :p Pas très compréhensible comme ça. Voici une version complète qui prend en compte mon petit PS:

L = crible_eratosthène(65535)

decomposer(m)
{
   F = liste des facteurs (initialement vide)

   pour chaque nombre l dans L
      si l divise m
         ajouter l à F
         m = m / l
         recommencer le test pour ce l-ci
      fin
   fin

   si F est vide
      ajouter m à F
   fin

   retourner F
}

NB: on n'a pas besoin de copier m au début de la fonction: si on a besoin de l'ajouter à F en fin de fonction, c'est que m n'a été divisé par aucun facteur l -> il est intact :)

Commentaire de Kirua le 15/11/2006 18:08:47

oups, désolé, j'ai oublié quelque chose:

      ...
      si l divise m
         ajouter l à F
         m = m / l
         si m = 1, sortir de la boucle
         recommencer le test pour ce l-ci
      fin
      ...

Commentaire de Matt67 le 16/11/2006 21:45:49

Bonsoir,

Kirua a dit : "long et int c'est pareil Joky [..]"

euh, je suis pas tout a fait d'accord : sizeof(short int) <= sizeof(int) <= sizeof(long int).
Il se peut que sizeof(int) == sizeof(long int) mais il se peut aussi que sizeof(int) != sizeof(long int).

Matt...

Commentaire de Kirua le 16/11/2006 23:52:31

C'est exact, mais dans la pratique, pour les compilos 32 bits que je connais, on a la propriété énoncée. Il y a le standard qui ne précise pas grand chose, et la réalité du terrain :) Si tu as besoin d'être sûr, une batterie de typedefs devraient faire l'affaire, non?

Enfin, je vais pas te reprocher de faire une précision, c'est tjs bon à prendre ^^.

Commentaire de NitRic le 24/11/2006 16:30:19

aujourd'hui y'a plus que le 32 bits, le 64 bits est arrivé

sous Windows 64 => int = 32 et long int = 32
microsoft avait utilisé int/long int à la random et donc voilà le résultat, il ne veut pas changer pour éviter les problèmes de portage 32 => 64

sous Linux 64 => int = 32 et long int = 64
linux a été plus intelligent et avait utilisé la règle des sizeof() mentionné par MATT67 plus haut

faut pas oublier qu'il n'y a que sous 32 bit où sizeof(int) == sizeof(long int)
sous Windows 16 bits par exemple, sizeof(int) était différent de sizeof(long int)

leurs tailles n'est pas fixes d'une platforme à une autre ...

Commentaire de Kirua le 25/11/2006 01:12:27

Ça n'a aucun lien avec l'OS il me semble, c'est seulement lié au compilateur. Pas besoin de transformer ça en troll linux.

Et éviter des problèmes de portage aussi importants que les types des int pour un langage (et un compilo) qui concerne quelques milliards sans doute de lignes de code, ça me paraît ... raisonnable.

Commentaire de BruNews le 25/11/2006 01:28:21 administrateur CS

Je trouve très bien qu'on n'ait pas changé les tailles.
J'exclus le 16 bits de la discussion.
Quand je vois int ou long dans un code, je sais que c'est 32 bits, je ne veux pas avoir à me poser la question du system cible, 32 ou 64 ces types seront définitivement 32 bits.
En prog Windows on n'a jamais employé 'long long' et autres bidules à rallonge, on emploie __int64, INT_PTR etc... le prob ne se pose donc pas car sont peut-être pas futés chez MS mais il y a tout de même de la continuité prévue.

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

premier prog C++ graphique et Dev C++ 4.0 [ par zoophage ] Salut !je suis plus ou moins débutant en C++ et c'est pour ça que j'utilise dev c++ qui a le mérite d'être gratuit et facile à utiliser.Seulement, voi Mettre une fenette en premier plan et l'activer [ par atao ] QQun connait il une façon plus élégnate pour mettre une fenette en premier plan et l'activervoid MettreFenetreDevant(HWND hwndDlg){// car si elle est Quelle API pour mettre en premier plan une autre fenetre ? [ par Kheo ] Afin d'eviter d'avoir plusieurs instance de mon soft en memoire au tout debut j'effectue un FindWindow sur le titre de mon soft. S'il ne trouve rien j connection entre deux projets [ par anaya ] Salut tout le mondeje travaille sur deux projets, le premier c'est une plate forme ecrite en c++( ce qui m'interesse dans celle-la un seul variable" t algorithme de gauss et decomposition LU [ par speedamine ] bonjour a tous.je voudrai avoir des algorithmes ,ecrits en borland pascal,suivants:methode de gauss ordinaire pour la resolution d'un systeme .la deco livres à proposer [ par chris5874 ] bonjour!je voudrais vous faire part de 2 livres qui m'ont aidé à commencer,car je trouve,bien expliquésle premier s'appelle le language c++ en 21 jour exercice tableau 2D pdcg et premier de deux entiers [ par ZeusRoot ] Melook Media enr.Voici ma question : Je suis un debutant en C et je voudrais savoir comment aborder ce exercice.Enonce1.- Pour un nombre e topmost sur une dialog [ par Manson ] Salut a tous,voila je cree une dialog comme ceci :h_info = CreateDialog((HINSTANCE)hInst, MAKEINTRESOURCE(IDD_INFO), hWnd, (DLGPROC)MakeProcInstance(( [win32] forcer une fenetre a rester en premier plan [ par tcok ] bonjour a tous,voila mon probleme, je developpe une application qui protege l'ordinateur sur lequel elle tourne, pendant l'absence de l'utilisateur, e Premier mot d'une chaine [ par daivil ] Bonsoir tout le monde,Je dois réaliser une fonction qui a le prototype suivnat :char *Premier (const T_Chaines ch);Et cette fonction doit me retourner


Nos sponsors


Sondage...

CalendriCode

Mars 2010
LMMJVSD
1234567
891011121314
15161718192021
22232425262728
293031    

Consulter la suite du CalendriCode
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,811 sec (4)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)