CodeS-SourceS est hébergé par Frontier.fr

Ce site au démarrage

begin process at 2012 02 05 05:26:07

Accueil Codes Tutoriels Forum Livres Emploi Services Connexion

Trouver un code source :

dans

[ Dernières recherches ]

Accueil >

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 :4 304

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

EDITER UN FICHIER BIT PAR BIT

Toutes les sources de riton91

Sources de la même categorie

UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras

CHIFFREMENT DE VIGENERE par lajouad

ANALYSE SYNTAXIQUE par lajouad

STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel

DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel

Toutes les sources de la catégorie Maths & Algorithmes

Sources en rapport avec celle ci

TROUVER LES NOMBRES PREMIERS INFÉRIEURS À UNE LIMITE DONNÉE par angrevol

FACTORISATION D'UN ENTIER EN PRODUIT DE NOMBRES PREMIERS AVE... par darkor

FACTORISATION D'UN NOMBRE EN NOMBRE PREMIER par Tearsofdestiny

FACTORISATION D'UN NOMBRE par Faibbus

GÉNÉRATION DE NOMBRES PREMIERS ET STOCKAGE DANS UN FICHIER par visdev

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

Derniers Blogs

CSS CONTENT STATE SELECTORS (PERSONNAL DRAFT) par FREMYCOMPANY

MBA : POURQUOI FAIRE ET COMMENT LE CHOISIR ? par ROMELARD Fabrice

Y'A DES ERREURS QUI PEUVENT RENDRE LE DéVELOPPEUR VIOLENT par Aleks

[HYPER-V 3] PRéSENTATION DES COMMANDLETS POWERSHELL par Pierrick CATRO-BROUILLET

IIS7 - COMPRESSION GZIP par cyril

Forum

RE : CRéATION D'UN AGENDA éLECTRONIQUE par taghssa

RE : [QT]JEUX SIMILAIRE à ZELDA EN MULTIJOUEUR par Neckara

AIDE PROBLEM DE COMPILATION par pboscaiolo

ARBRE BINAIRE par pacotheking

RE : RéCUPéRER UN CHAMP D'UN QTABLEVIEW DANS UN QLINEEDIT par mature

Côté IT

Offres d'emploi

Formations Video

Appels d'offres

Cherche referenceur astucieux
Budget : 1 500€
Recherche expert advisor sous mql4 hedging
Budget : 200€
Creation boutique en ligne iphone- android - Republication.
Budget : 4 000€

Logiciels

Easy-Planning (1.0.0.1)
EASY-PLANNING (1.0.0.1)

Basé sur les mêmes principes que MyPlanning, Easy-Planning permet de créer des plannings sous la ...

Cliquez pour télécharger Easy-Planning
Academy System (17.1.3.0)
ACADEMY SYSTEM (17.1.3.0)

Logiciel de gestion des établissements. - élèves/étudiants (inscription, dossier, absence...) -...

Cliquez pour télécharger Academy System
COLLECTOR PLUS (3.00B)
COLLECTOR PLUS (3.00B)

COLLECTOR PLUS version 3.00B est un logiciel utilisant une base de données alimentée par : - L...

Cliquez pour télécharger COLLECTOR PLUS
PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V7.4)
PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V7.4)

PONAMEDIA TV DEVIENS HELLLOOO FLASH LA TV SUR VOTRE ORDINATEUR. Toute une plateforme Multi...

Cliquez pour télécharger PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO
LettresFaciles 2011 (8.0.0.1)
LETTRESFACILES 2011 (8.0.0.1)

LettresFaciles est un logiciel facilitant la création et la rédaction de lettres types. Son inte...

Cliquez pour télécharger LettresFaciles 2011