Menemukan Kelipatan Persekutuan Terkecil di Java

1. Ikhtisar

Kelipatan Persekutuan Terkecil (KPK) dari dua bilangan bulat bukan nol (a, b) adalah bilangan bulat positif terkecil yang habis habis dibagi oleh a dan b .

Dalam tutorial ini, kita akan belajar tentang berbagai pendekatan untuk menemukan KPK dari dua atau lebih bilangan. Kita harus mencatat bahwa bilangan bulat negatif dan nol bukanlah kandidat untuk LCM .

2. Menghitung KPK dari Dua Bilangan Menggunakan Algoritma Sederhana

Kita dapat mencari KPK dari dua bilangan dengan menggunakan fakta sederhana bahwa perkalian adalah penjumlahan berulang .

2.1. Algoritma

Algoritme sederhana untuk mencari KPK adalah pendekatan berulang yang menggunakan beberapa properti dasar KPK dari dua bilangan.

Pertama, kita tahu bahwa KPK dari bilangan apa pun dengan nol adalah nol itu sendiri. Jadi, kita bisa keluar lebih awal dari prosedur setiap kali salah satu bilangan bulat yang diberikan adalah 0.

Kedua, kita juga dapat menggunakan fakta bahwa batas bawah KPK dari dua bilangan bulat bukan nol lebih besar dari nilai absolut kedua bilangan tersebut .

Selain itu, seperti yang dijelaskan sebelumnya, KPK tidak pernah bisa menjadi bilangan bulat negatif. Jadi, kita hanya akan menggunakan nilai absolut dari bilangan bulat untuk menemukan kemungkinan kelipatannya sampai kita menemukan kelipatan persekutuan.

Mari kita lihat prosedur pasti yang perlu kita ikuti untuk menentukan lcm (a, b):

  1. Jika a = 0 atau b = 0, maka kembali dengan lcm (a, b) = 0, jika tidak lanjutkan ke langkah 2.
  2. Hitung nilai absolut dari kedua angka tersebut.
  3. Inisialisasi lcm sebagai nilai yang lebih tinggi dari dua nilai yang dihitung pada langkah 2.
  4. Jika lcm habis dibagi nilai absolut yang lebih rendah, maka kembalikan.
  5. Naikkan lcm dengan nilai absolut yang lebih tinggi di antara keduanya dan lanjutkan ke langkah 4.

Sebelum kita mulai dengan penerapan pendekatan sederhana ini, mari kita lakukan uji coba untuk menemukan lcm (12, 18).

Karena 12 dan 18 positif, mari lompat ke langkah 3, inisialisasi lcm = max (12, 18) = 18, dan lanjutkan lebih jauh.

Dalam iterasi pertama kita, lcm = 18, yang tidak habis habis dibagi 12. Jadi, kita naikkan menjadi 18 dan lanjutkan.

Pada iterasi kedua, kita dapat melihat bahwa lcm = 36 dan sekarang habis habis dibagi 12. Jadi, kita dapat kembali dari algoritme dan menyimpulkan bahwa lcm (12, 18) adalah 36.

2.2. Penerapan

Mari implementasikan algoritme di Java. Kami lcm () metode kebutuhan untuk menerima dua argumen integer dan memberikan LCM mereka sebagai nilai kembali.

Kita dapat melihat bahwa algoritma di atas melibatkan melakukan beberapa operasi matematika pada angka-angka seperti menemukan nilai absolut, minimum, dan maksimum. Untuk tujuan ini, kita dapat menggunakan metode statis yang sesuai dari kelas Matematika seperti abs () , min (), dan max () , masing-masing.

Mari terapkan metode lcm () kita :

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; }

Selanjutnya, mari kita juga memvalidasi metode ini:

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

Kasus uji di atas memverifikasi kebenaran metode lcm () dengan menyatakan bahwa lcm (12, 18) adalah 36.

3. Menggunakan Pendekatan Faktorisasi Prima

Teorema dasar aritmatika menyatakan bahwa setiap bilangan bulat yang lebih besar dari satu dapat diekspresikan secara unik sebagai hasil kali dari pangkat bilangan prima.

Jadi, untuk bilangan bulat N> 1, kami memiliki N = (2k1) * (3k2) * (5k3) *…

Dengan menggunakan hasil dari teorema ini, sekarang kita akan memahami pendekatan faktorisasi prima untuk mencari KPK dari dua bilangan.

3.1. Algoritma

Pendekatan faktorisasi prima menghitung KPK dari dekomposisi prima kedua bilangan tersebut. Kita dapat menggunakan faktor prima dan eksponen dari faktorisasi prima untuk menghitung KPK dari dua bilangan:

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

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

then, lcm(a, b) = (2max(p1, q1)) * (3max(p2, q2)) * (5max(p3, q3)) …

Let's see how to calculate the LCM of 12 and 18 using this approach:

Firstly, we need to represent the absolute values of the two numbers as products of prime factors:

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

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

We can notice here that the prime factors in the above representations are 2 and 3.

Next, let's determine the exponent of each prime factor for the LCM. We do this by taking its higher power from the two representations.

Using this strategy, the power of 2 in the LCM will be max(2, 1) = 2, and the power of 3 in the LCM will be max(1, 2) = 2.

Finally, we can compute the LCM by multiplying the prime factors with a corresponding power obtained in the previous step. Consequently, we have lcm(12, 18) = 2² * 3² = 36.

3.2. Implementation

Our Java implementation uses prime factorization representation of the two numbers to find the LCM.

For this purpose, our getPrimeFactors() method needs to accept an integer argument and give us its prime factorization representation. In Java, we can represent prime factorization of a number using a HashMap where each key denotes the prime factor and the value associated with the key signifies the exponent of the corresponding factor.

Let's see an iterative implementation of the getPrimeFactors() method:

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.

Seperti biasa, kode sumber lengkap untuk implementasi Java yang digunakan dalam artikel ini tersedia di GitHub.