Discussion :

[KORTA]

Salut a tous,
je cherche le plus petit commun multiple d'un entier a avec b, (ppcm(a,b))
Quelqu'un connait une facon de l'implémenter de facon optimale ?
A bientot et merci d'avance aux réponses données

[snyff]

par récurrence :

soit de nombre a et b :
tu choisi le plus petit ( on suppose a ) avec un if


et aprés tu fais :
c = a - 1

- si c multiple de a et b alors fin
- sinon essayer avec c - 1

grosso modo ça doit déjà pas être mal :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int multiple( int a , int b, int c ) 
{
  if (( a % c == 0 ) && ( b % c ==0 ))
 
         {
          return(c);  
          }
   else
          {
           multiple(a,b,c-1);
           }
}

bien sur ça peut etre encore améliorer ( le passage de a et b en variables globales ) mais c'est déjà plus que du pré-macher

[KORTA]

je pas suis sur que ce soit optimal , si imaginons qu'on travaille avec des grands chiffres...
En fait apres reflexion, je me suis rappelé que
ppcm(a,b)=(a*b)/pgcd(a,b);
et pgcd(a,b) se calcule en O(log(max(a,b)) donc pareil pour le ppcm ..
Si quelqu'un voit mieux?

[snyff]

bien vu, là c'est sur que tu as raison et que l'on peut pas trouver mieux à mon avis .