Trovare il minimo comune multiplo in Java

1. Panoramica

Il minimo comune multiplo (LCM) di due numeri interi diversi da zero (a, b) è il più piccolo numero intero positivo perfettamente divisibile sia per a che per b .

In questo tutorial, impareremo diversi approcci per trovare il LCM di due o più numeri. Dobbiamo notare che i numeri interi negativi e zero non sono candidati per LCM .

2. Calcolo di LCM di due numeri utilizzando un semplice algoritmo

Possiamo trovare l'MCM di due numeri usando il semplice fatto che la moltiplicazione è un'addizione ripetuta .

2.1. Algoritmo

Il semplice algoritmo per trovare l'LCM è un approccio iterativo che fa uso di alcune proprietà fondamentali dell'LCM di due numeri.

In primo luogo, sappiamo che il LCM di qualsiasi numero con zero è zero stesso. Quindi, possiamo uscire anticipatamente dalla procedura ogni volta che uno degli interi dati è 0.

In secondo luogo, possiamo anche utilizzare il fatto che il limite inferiore del LCM di due numeri interi diversi da zero è il maggiore dei valori assoluti dei due numeri .

Inoltre, come spiegato in precedenza, il LCM non può mai essere un numero intero negativo. Quindi, utilizzeremo solo i valori assoluti degli interi per trovare i possibili multipli finché non troviamo un multiplo comune.

Vediamo la procedura esatta che dobbiamo seguire per determinare mcm (a, b):

  1. Se a = 0 o b = 0, torna con mcm (a, b) = 0, altrimenti vai al passaggio 2.
  2. Calcola i valori assoluti dei due numeri.
  3. Inizializza lcm come il più alto dei due valori calcolati nel passaggio 2.
  4. Se mcm è divisibile per il valore assoluto inferiore, restituisci.
  5. Aumentare mcm del valore assoluto più alto tra i due e andare al passaggio 4.

Prima di iniziare con l'implementazione di questo semplice approccio, eseguiamo una prova a vuoto per trovare mcm (12, 18).

Poiché sia ​​12 che 18 sono positivi, saltiamo al passaggio 3, inizializzando mcm = max (12, 18) = 18 e procediamo oltre.

Nella nostra prima iterazione, mcm = 18, che non è perfettamente divisibile per 12. Quindi, lo incrementiamo di 18 e continuiamo.

Nella seconda iterazione, possiamo vedere che mcm = 36 ed è ora perfettamente divisibile per 12. Quindi, possiamo tornare dall'algoritmo e concludere che mcm (12, 18) è 36.

2.2. Implementazione

Implementiamo l'algoritmo in Java. Il nostro metodo lcm () deve accettare due argomenti interi e fornire il loro LCM come valore di ritorno.

Possiamo notare che l'algoritmo di cui sopra comporta l'esecuzione di alcune operazioni matematiche sui numeri come la ricerca di valori assoluti, minimi e massimi. A questo scopo, possiamo utilizzare i metodi statici corrispondenti della classe Math come abs () , min () e max () , rispettivamente.

Implementiamo il nostro metodo 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; }

Successivamente, convalidiamo anche questo metodo:

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

Il caso di test precedente verifica la correttezza del metodo mcm () affermando che mcm (12, 18) è 36.

3. Utilizzo dell'approccio di fattorizzazione primaria

Il teorema fondamentale dell'aritmetica afferma che è possibile esprimere in modo univoco ogni intero maggiore di uno come prodotto delle potenze dei numeri primi.

Quindi, per ogni numero intero N> 1, abbiamo N = (2k1) * (3k2) * (5k3) * ...

Usando il risultato di questo teorema, ora comprenderemo l'approccio della scomposizione in fattori primi per trovare l'MCM di due numeri.

3.1. Algoritmo

L'approccio della scomposizione in fattori primi calcola il LCM dalla scomposizione in primi dei due numeri. Possiamo utilizzare i fattori primi e gli esponenti della scomposizione in fattori primi per calcolare l'MCL dei due numeri:

Quando, | a | = (2p1) * (3p2) * (5p3) * ...

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

quindi, mcm (a, b) = (2max (p 1 , q 1 )) * (3max (p 2 , q 2 )) * (5max (p 3 , q 3 )) ...

Vediamo come calcolare il LCM di 12 e 18 utilizzando questo approccio:

Innanzitutto, dobbiamo rappresentare i valori assoluti dei due numeri come prodotti di fattori primi:

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

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

Possiamo notare qui che i fattori primi nelle rappresentazioni precedenti sono 2 e 3.

Successivamente, determiniamo l'esponente di ciascun fattore primo per il LCM. Lo facciamo prendendo il suo potere più alto dalle due rappresentazioni.

Usando questa strategia, la potenza di 2 nel LCM sarà max (2, 1) = 2 e la potenza di 3 nel LCM sarà max (1, 2) = 2.

Infine, possiamo calcolare il LCM moltiplicando i fattori primi per una potenza corrispondente ottenuta nel passaggio precedente. Di conseguenza, abbiamo mcm (12, 18) = 2² * 3² = 36.

3.2. Implementazione

La nostra implementazione Java utilizza la rappresentazione in fattori primi dei due numeri per trovare il LCM.

A tal fine, il nostro metodo getPrimeFactors () deve accettare un argomento intero e fornirci la sua rappresentazione in fattori primi. In Java, possiamo rappresentare la scomposizione in fattori primi di un numero utilizzando una HashMap in cui ogni chiave indica il fattore primo e il valore associato alla chiave indica l'esponente del fattore corrispondente.

Vediamo un'implementazione iterativa del metodo 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.

Come sempre, il codice sorgente completo per l'implementazione Java utilizzata in questo articolo è disponibile su GitHub.