Les fonctions lcm et gcd sont des fonctions mathématiques courantes qui permettent de calculer respectivement le plus petit commun multiple et le plus grand commun diviseur de deux nombres entiers. Ces fonctions sont présentes dans de nombreux langages de programmation, y compris Haskell.
La fonction lcm (pour least common multiple) retourne le plus petit nombre entier qui est un multiple commun de deux nombres donnés. La fonction gcd (pour greatest common divisor) retourne le plus grand diviseur commun à deux nombres donnés.
En Haskell, ces fonctions sont implémentées dans le module Data.List. Voici un exemple d'utilisation de ces fonctions :
import Data.List (lcm, gcd)
-- Calcul du ppcm de deux nombres
ppcm x y = lcm x y
-- Calcul du pgcd de deux nombres
pgcd x y = gcd x y
Dans cet exemple, la fonction ppcm utilise la fonction lcm pour calculer le ppcm de deux nombres, et la fonction pgcd utilise la fonction gcd pour calculer le pgcd de deux nombres.
Il est également possible d'implémenter ces fonctions de manière récursive. Voici un exemple d'implémentation récursive de la fonction gcd :
gcd' :: Int -> Int -> Int
gcd' a b
| b == 0 = abs a
| otherwise = gcd' b (a `mod` b)
Dans cette implémentation, la fonction est récursive et utilise l'algorithme d'Euclide pour calculer le pgcd de deux nombres entiers. L'algorithme d'Euclide consiste à répéter la division euclidienne du plus grand nombre par le plus petit nombre, jusqu'à ce que le reste soit égal à zéro. Le dernier diviseur non nul est alors le pgcd des deux nombres.
Il est important de noter que la fonction gcd implémentée de cette manière peut également être utilisée pour calculer le pgcd de plusieurs nombres, en appelant récursivement la fonction avec les nombres successifs.
