Recherche du multiple le moins commun en Java

1. Vue d'ensemble

Le plus petit commun multiple (LCM) de deux entiers non nuls (a, b) est le plus petit entier positif parfaitement divisible par a et b .

Dans ce didacticiel, nous allons découvrir différentes approches pour trouver le LCM de deux nombres ou plus. Il faut noter que les entiers négatifs et zéro ne sont pas des candidats pour LCM .

2. Calcul du LCM de deux nombres à l'aide d'un algorithme simple

Nous pouvons trouver le LCM de deux nombres en utilisant le simple fait que la multiplication est une addition répétée .

2.1. Algorithme

L'algorithme simple pour trouver le LCM est une approche itérative qui utilise quelques propriétés fondamentales du LCM à deux nombres.

Premièrement, nous savons que le LCM de tout nombre avec zéro est zéro lui-même. Ainsi, nous pouvons faire une sortie anticipée de la procédure chaque fois que l'un des nombres entiers donnés est 0.

Deuxièmement, nous pouvons également utiliser le fait que la borne inférieure du LCM de deux entiers non nuls est la plus grande des valeurs absolues des deux nombres .

De plus, comme expliqué précédemment, le LCM ne peut jamais être un entier négatif. Nous n'utiliserons donc que les valeurs absolues des entiers pour trouver les multiples possibles jusqu'à ce que nous trouvions un multiple commun.

Voyons la procédure exacte que nous devons suivre pour déterminer lcm (a, b):

  1. Si a = 0 ou b = 0, alors retournez avec lcm (a, b) = 0, sinon passez à l'étape 2.
  2. Calculez les valeurs absolues des deux nombres.
  3. Initialisez lcm comme étant la plus élevée des deux valeurs calculées à l'étape 2.
  4. Si lcm est divisible par la valeur absolue inférieure, alors retourne.
  5. Incrémentez lcm de la valeur absolue la plus élevée parmi les deux et passez à l'étape 4.

Avant de commencer avec la mise en œuvre de cette approche simple, faisons un essai pour trouver lcm (12, 18).

Comme 12 et 18 sont tous deux positifs, passons à l'étape 3, initialisant lcm = max (12, 18) = 18, et continuez.

Dans notre première itération, lcm = 18, qui n'est pas parfaitement divisible par 12. Nous l'incrémentons donc de 18 et continuons.

Dans la deuxième itération, nous pouvons voir que lcm = 36 et est maintenant parfaitement divisible par 12. Nous pouvons donc revenir de l'algorithme et conclure que lcm (12, 18) est 36.

2.2. la mise en oeuvre

Implémentons l'algorithme en Java. Notre méthode lcm () doit accepter deux arguments entiers et donner leur LCM comme valeur de retour.

Nous pouvons remarquer que l'algorithme ci-dessus implique d'effectuer quelques opérations mathématiques sur les nombres telles que la recherche de valeurs absolues, minimales et maximales. Pour cela, nous pouvons utiliser les méthodes statiques correspondantes de la classe Math telles que abs () , min () et max () , respectivement.

Implémentons notre méthode lcm () :

public static int lcm(int number1, int number2) { if (number1 == 0 || number2 == 0) { return 0; } int absNumber1 = Math.abs(number1); int absNumber2 = Math.abs(number2); int absHigherNumber = Math.max(absNumber1, absNumber2); int absLowerNumber = Math.min(absNumber1, absNumber2); int lcm = absHigherNumber; while (lcm % absLowerNumber != 0) { lcm += absHigherNumber; } return lcm; }

Ensuite, validons également cette méthode:

@Test public void testLCM() { Assert.assertEquals(36, lcm(12, 18)); }

Le cas de test ci-dessus vérifie l'exactitude de la méthode lcm () en affirmant que lcm (12, 18) vaut 36.

3. Utilisation de l'approche de factorisation principale

Le théorème fondamental de l'arithmétique stipule qu'il est possible d'exprimer de manière unique chaque entier supérieur à un comme un produit de puissances de nombres premiers.

Donc, pour tout entier N> 1, on a N = (2k1) * (3k2) * (5k3) *…

En utilisant le résultat de ce théorème, nous allons maintenant comprendre l'approche de factorisation des nombres premiers pour trouver le LCM de deux nombres.

3.1. Algorithme

L'approche de factorisation première calcule le LCM à partir de la décomposition première des deux nombres. Nous pouvons utiliser les facteurs premiers et les exposants de la factorisation première pour calculer le LCM des deux nombres:

Quand, | a | = (2p1) * (3p2) * (5p3) *…

et | b | = (2q1) * (3q2) * (5q3) *…

alors, lcm (a, b) = (2max (p 1 , q 1 )) * (3max (p 2 , q 2 )) * (5max (p 3 , q 3 ))…

Voyons comment calculer le LCM de 12 et 18 en utilisant cette approche:

Premièrement, nous devons représenter les valeurs absolues des deux nombres comme des produits de facteurs premiers:

12 = 2 * 2 * 3 = 2² * 3¹

18 = 2 * 3 * 3 = 2¹ * 3²

Nous pouvons remarquer ici que les facteurs premiers dans les représentations ci-dessus sont 2 et 3.

Ensuite, déterminons l'exposant de chaque facteur premier pour le LCM. Nous faisons cela en prenant sa puissance supérieure des deux représentations.

En utilisant cette stratégie, la puissance de 2 dans le LCM sera max (2, 1) = 2, et la puissance de 3 dans le LCM sera max (1, 2) = 2.

Enfin, nous pouvons calculer le LCM en multipliant les facteurs premiers par une puissance correspondante obtenue à l'étape précédente. Par conséquent, nous avons lcm (12, 18) = 2² * 3² = 36.

3.2. la mise en oeuvre

Notre implémentation Java utilise la représentation par factorisation première des deux nombres pour trouver le LCM.

Pour cela, notre méthode getPrimeFactors () doit accepter un argument entier et nous donner sa représentation de factorisation première. En Java, nous pouvons représenter la factorisation premier d'un nombre à l'aide d'un HashMap où chaque clé désigne le facteur premier et la valeur associée à la clé signifie l'exposant du facteur correspondant.

Voyons une implémentation itérative de la méthode getPrimeFactors () :

public static Map getPrimeFactors(int number) { int absNumber = Math.abs(number); Map primeFactorsMap = new HashMap(); for (int factor = 2; factor <= absNumber; factor++) { while (absNumber % factor == 0) { Integer power = primeFactorsMap.get(factor); if (power == null) { power = 0; } primeFactorsMap.put(factor, power + 1); absNumber /= factor; } } return primeFactorsMap; }

We know that the prime factorization maps of 12 and 18 are {2 → 2, 3 → 1} and {2 → 1, 3 → 2} respectively. Let's use this to test the above method:

@Test public void testGetPrimeFactors() { Map expectedPrimeFactorsMapForTwelve = new HashMap(); expectedPrimeFactorsMapForTwelve.put(2, 2); expectedPrimeFactorsMapForTwelve.put(3, 1); Assert.assertEquals(expectedPrimeFactorsMapForTwelve, PrimeFactorizationAlgorithm.getPrimeFactors(12)); Map expectedPrimeFactorsMapForEighteen = new HashMap(); expectedPrimeFactorsMapForEighteen.put(2, 1); expectedPrimeFactorsMapForEighteen.put(3, 2); Assert.assertEquals(expectedPrimeFactorsMapForEighteen, PrimeFactorizationAlgorithm.getPrimeFactors(18)); }

Our lcm() method first uses the getPrimeFactors() method to find prime factorization map for each number. Next, it uses the prime factorization map of both the numbers to find their LCM. Let's see an iterative implementation of this method:

public static int lcm(int number1, int number2) { if(number1 == 0 || number2 == 0) { return 0; } Map primeFactorsForNum1 = getPrimeFactors(number1); Map primeFactorsForNum2 = getPrimeFactors(number2); Set primeFactorsUnionSet = new HashSet(primeFactorsForNum1.keySet()); primeFactorsUnionSet.addAll(primeFactorsForNum2.keySet()); int lcm = 1; for (Integer primeFactor : primeFactorsUnionSet) { lcm *= Math.pow(primeFactor, Math.max(primeFactorsForNum1.getOrDefault(primeFactor, 0), primeFactorsForNum2.getOrDefault(primeFactor, 0))); } return lcm; }

As a good practice, we shall now verify the logical correctness of the lcm() method:

@Test public void testLCM() { Assert.assertEquals(36, PrimeFactorizationAlgorithm.lcm(12, 18)); }

4. Using the Euclidean Algorithm

There's an interesting relation between the LCM and GCD (Greatest Common Divisor) of two numbers that says that the absolute value of the product of two numbers is equal to the product of their GCD and LCM.

As stated, gcd(a, b) * lcm(a, b) = |a * b|.

Consequently, lcm(a, b) = |a * b|/gcd(a, b).

Using this formula, our original problem of finding lcm(a,b) has now been reduced to just finding gcd(a,b).

Granted, there are multiple strategies to finding GCD of two numbers. However, the Euclidean algorithm is known to be one of the most efficient of all.

For this reason, let's briefly understand the crux of this algorithm, which can be summed up in two relations:

  • gcd (a, b) = gcd(|a%b|, |a| ); where |a| >= |b|
  • gcd(p, 0) = gcd(0, p) = |p|

Let's see how we can find lcm(12, 18) using the above relations:

We have gcd(12, 18) = gcd(18%12, 12) = gcd(6,12) = gcd(12%6, 6) = gcd(0, 6) = 6

Therefore, lcm(12, 18) = |12 x 18| / gcd(12, 18) = (12 x 18) / 6 = 36

We'll now see a recursive implementation of the Euclidean algorithm:

public static int gcd(int number1, int number2) { if (number1 == 0 || number2 == 0) { return number1 + number2; } else { int absNumber1 = Math.abs(number1); int absNumber2 = Math.abs(number2); int biggerValue = Math.max(absNumber1, absNumber2); int smallerValue = Math.min(absNumber1, absNumber2); return gcd(biggerValue % smallerValue, smallerValue); } }

The above implementation uses the absolute values of numbers — since GCD is the largest positive integer that perfectly divides the two numbers, we're not interested in negative divisors.

We're now ready to verify if the above implementation works as expected:

@Test public void testGCD() { Assert.assertEquals(6, EuclideanAlgorithm.gcd(12, 18)); }

4.1. LCM of Two Numbers

Using the earlier method to find GCD, we can now easily calculate LCM. Again, our lcm() method needs to accept two integers as input to return their LCM. Let's see how we can implement this method in Java:

public static int lcm(int number1, int number2) { if (number1 == 0 || number2 == 0) return 0; else { int gcd = gcd(number1, number2); return Math.abs(number1 * number2) / gcd; } }

We can now verify the functionality of the above method:

@Test public void testLCM() { Assert.assertEquals(36, EuclideanAlgorithm.lcm(12, 18)); }

4.2. LCM of Large Numbers Using the BigInteger Class

To calculate the LCM of large numbers, we can leverage the BigInteger class.

Internally, the gcd() method of the BigInteger class uses a hybrid algorithm to optimize computation performance. Moreover, since the BigInteger objects are immutable, the implementation leverages mutable instances of the MutableBigInteger class to avoid frequent memory reallocations.

To begin with, it uses the conventional Euclidean algorithm to repeatedly replace the higher integer by its modulus with the lower integer.

As a result, the pair not only gets smaller and smaller but also closer to each other after successive divisions. Eventually, the difference in the number of ints required to hold the magnitude of the two MutableBigInteger objects in their respective int[] value arrays reaches either 1 or 0.

At this stage, the strategy is switched to the Binary GCD algorithm to get even faster computation results.

In this case, as well, we'll compute LCM by dividing the absolute value of the product of the numbers by their GCD. Similar to our prior examples, our lcm() method takes two BigInteger values as input and returns the LCM for the two numbers as a BigInteger. Let's see it in action:

public static BigInteger lcm(BigInteger number1, BigInteger number2) { BigInteger gcd = number1.gcd(number2); BigInteger absProduct = number1.multiply(number2).abs(); return absProduct.divide(gcd); }

Finally, we can verify this with a test case:

@Test public void testLCM() { BigInteger number1 = new BigInteger("12"); BigInteger number2 = new BigInteger("18"); BigInteger expectedLCM = new BigInteger("36"); Assert.assertEquals(expectedLCM, BigIntegerLCM.lcm(number1, number2)); }

5. Conclusion

In this tutorial, we discussed various methods to find the least common multiple of two numbers in Java.

Moreover, we also learned about the relation between the product of numbers with their LCM and GCD. Given algorithms that can compute the GCD of two numbers efficiently, we've also reduced the problem of LCM calculation to one of GCD computation.

Comme toujours, le code source complet de l'implémentation Java utilisée dans cet article est disponible sur GitHub.