DÉCOMPOSITION D'UN NOMBRE EN PUISSANCE DE FACTEURS PREMIERS
BruNews
Messages postés
21040
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
-
14 nov. 2006 à 23:29
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 - 25 nov. 2006 à 01:28
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 - 25 nov. 2006 à 01:28
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/40318-decomposition-d-un-nombre-en-puissance-de-facteurs-premiers
https://codes-sources.commentcamarche.net/source/40318-decomposition-d-un-nombre-en-puissance-de-facteurs-premiers
25 nov. 2006 à 01:28
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.
25 nov. 2006 à 01:12
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.
24 nov. 2006 à 16:30
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 ...
16 nov. 2006 à 23:52
Enfin, je vais pas te reprocher de faire une précision, c'est tjs bon à prendre ^^.
16 nov. 2006 à 21:45
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...
15 nov. 2006 à 18:08
...
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
...
15 nov. 2006 à 17:56
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 :)
15 nov. 2006 à 17:50
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.
15 nov. 2006 à 17:22
Etrange:)
15 nov. 2006 à 16:52
En réalité, int et long sont des synonymes pour long int, et long long est un synonyme de long long int.
15 nov. 2006 à 16:09
15 nov. 2006 à 16:06
15 nov. 2006 à 10:59
14 nov. 2006 à 23:29
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.