Skip to content

Commit 0467201

Browse files
tapankavasthitapankavasthi
committed
BAEL-3116: Finding the Least Common Multiple in Java
- Add tutorial to implement algorithms used for computing LCM of two or more numbers. - List of Algorithms covered: - Simple Method - Prime Factorization Method - Euclidean Algorithm - BigInteger Class for large numbers - Lambda Implementation for LCM of more than two numbers - Reference: BAEL-3116
1 parent 181943a commit 0467201

8 files changed

Lines changed: 203 additions & 0 deletions

File tree

‎java-numbers-2/src/main/java/com/baeldung/lcm/BigIntegerLCM.java‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package com.baeldung.lcm;
2+
3+
import java.math.BigInteger;
4+
5+
public class BigIntegerLCM {
6+
7+
public static BigInteger lcm(BigInteger number1, BigInteger number2) {
8+
BigInteger gcd = number1.gcd(number2);
9+
BigInteger absProduct = number1.multiply(number2).abs();
10+
return absProduct.divide(gcd);
11+
}
12+
13+
}

‎java-numbers-2/src/main/java/com/baeldung/lcm/EuclideanAlgorithm.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package com.baeldung.lcm;
2+
3+
import java.util.Arrays;
4+
5+
public class EuclideanAlgorithm {
6+
7+
public static int gcd(int number1, int number2) {
8+
if (number1 == 0 || number2 == 0) {
9+
return number1 + number2;
10+
} else {
11+
int absNumber1 = Math.abs(number1);
12+
int absNumber2 = Math.abs(number2);
13+
int biggerValue = Math.max(absNumber1, absNumber2);
14+
int smallerValue = Math.min(absNumber1, absNumber2);
15+
return gcd(biggerValue % smallerValue, smallerValue);
16+
}
17+
}
18+
19+
public static int lcm(int number1, int number2) {
20+
if (number1 == 0 || number2 == 0)
21+
return 0;
22+
else {
23+
int gcd = gcd(number1, number2);
24+
return Math.abs(number1 * number2) / gcd;
25+
}
26+
}
27+
28+
public static int lcmForArray(int[] numbers) {
29+
int lcm = numbers[0];
30+
for (int i = 1; i <= numbers.length - 1; i++) {
31+
lcm = lcm(lcm, numbers[i]);
32+
}
33+
return lcm;
34+
}
35+
36+
public static int lcmByLambda(int... numbers) {
37+
return Arrays.stream(numbers).reduce(1, (lcmSoFar, currentNumber) -> Math.abs(lcmSoFar * currentNumber) / gcd(lcmSoFar, currentNumber));
38+
}
39+
40+
}

‎java-numbers-2/src/main/java/com/baeldung/lcm/PrimeFactorizationAlgorithm.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.baeldung.lcm;
2+
3+
import java.util.HashMap;
4+
import java.util.HashSet;
5+
import java.util.Map;
6+
import java.util.Set;
7+
8+
public class PrimeFactorizationAlgorithm {
9+
10+
public static Map<Integer, Integer> getPrimeFactors(int number) {
11+
int absNumber = Math.abs(number);
12+
Map<Integer, Integer> primeFactorsMap = new HashMap<Integer, Integer>();
13+
for (int factor = 2; factor <= absNumber; factor++) {
14+
while (absNumber % factor == 0) {
15+
Integer power = primeFactorsMap.get(factor);
16+
if (power == null) {
17+
power = 0;
18+
}
19+
primeFactorsMap.put(factor, power + 1);
20+
absNumber /= factor;
21+
}
22+
}
23+
return primeFactorsMap;
24+
}
25+
26+
public static int lcm(int number1, int number2) {
27+
if (number1 == 0 || number2 == 0) {
28+
return 0;
29+
}
30+
Map<Integer, Integer> primeFactorsForNum1 = getPrimeFactors(number1);
31+
Map<Integer, Integer> primeFactorsForNum2 = getPrimeFactors(number2);
32+
Set<Integer> primeFactorsUnionSet = new HashSet<Integer>(primeFactorsForNum1.keySet());
33+
primeFactorsUnionSet.addAll(primeFactorsForNum2.keySet());
34+
int lcm = 1;
35+
for (Integer primeFactor : primeFactorsUnionSet) {
36+
lcm *= Math.pow(primeFactor, Math.max(primeFactorsForNum1.getOrDefault(primeFactor, 0),
37+
primeFactorsForNum2.getOrDefault(primeFactor, 0)));
38+
}
39+
return lcm;
40+
}
41+
42+
}

‎java-numbers-2/src/main/java/com/baeldung/lcm/SimpleAlgorithm.java‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
package com.baeldung.lcm;
2+
3+
public class SimpleAlgorithm {
4+
public static int lcm(int number1, int number2) {
5+
if (number1 == 0 || number2 == 0) {
6+
return 0;
7+
}
8+
int absNumber1 = Math.abs(number1);
9+
int absNumber2 = Math.abs(number2);
10+
int absHigherNumber = Math.max(absNumber1, absNumber2);
11+
int absLowerNumber = Math.min(absNumber1, absNumber2);
12+
int lcm = absHigherNumber;
13+
while (lcm % absLowerNumber != 0) {
14+
lcm += absHigherNumber;
15+
}
16+
return lcm;
17+
}
18+
}

‎java-numbers-2/src/test/java/com/baeldung/lcm/BigIntegerLCMUnitTest.java‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
package com.baeldung.lcm;
2+
3+
4+
import org.junit.Assert;
5+
import org.junit.Test;
6+
7+
import java.math.BigInteger;
8+
9+
public class BigIntegerLCMUnitTest {
10+
11+
@Test
12+
public void testLCM() {
13+
BigInteger number1 = new BigInteger("12");
14+
BigInteger number2 = new BigInteger("18");
15+
BigInteger expectedLCM = new BigInteger("36");
16+
Assert.assertEquals(expectedLCM, BigIntegerLCM.lcm(number1, number2));
17+
}
18+
}

‎java-numbers-2/src/test/java/com/baeldung/lcm/EuclideanAlgorithmUnitTest.java‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package com.baeldung.lcm;
2+
3+
import org.junit.Assert;
4+
import org.junit.Test;
5+
6+
public class EuclideanAlgorithmUnitTest {
7+
8+
@Test
9+
public void testGCD() {
10+
Assert.assertEquals(6, EuclideanAlgorithm.gcd(12, 18));
11+
}
12+
13+
@Test
14+
public void testLCM() {
15+
Assert.assertEquals(36, EuclideanAlgorithm.lcm(12, 18));
16+
}
17+
18+
@Test
19+
public void testLCMForArray() {
20+
Assert.assertEquals(15, EuclideanAlgorithm.lcmForArray(new int[]{3, 5, 15}));
21+
}
22+
23+
@Test
24+
public void testLCMByLambdaForArray() {
25+
Assert.assertEquals(15, EuclideanAlgorithm.lcmByLambda(new int[]{3, 5, 15}));
26+
}
27+
}

‎java-numbers-2/src/test/java/com/baeldung/lcm/PrimeFactorizationAlgorithmUnitTest.java‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package com.baeldung.lcm;
2+
3+
import org.junit.Assert;
4+
import org.junit.Test;
5+
6+
import java.util.HashMap;
7+
import java.util.Map;
8+
9+
import static com.baeldung.lcm.PrimeFactorizationAlgorithm.*;
10+
11+
12+
public class PrimeFactorizationAlgorithmUnitTest {
13+
14+
@Test
15+
public void testGetPrimeFactors() {
16+
Map<Integer, Integer> expectedPrimeFactorsMapForTwelve = new HashMap<>();
17+
expectedPrimeFactorsMapForTwelve.put(2, 2);
18+
expectedPrimeFactorsMapForTwelve.put(3, 1);
19+
Map<Integer, Integer> expectedPrimeFactorsMapForEighteen = new HashMap<>();
20+
expectedPrimeFactorsMapForEighteen.put(2, 1);
21+
expectedPrimeFactorsMapForEighteen.put(3, 2);
22+
Assert.assertEquals(expectedPrimeFactorsMapForTwelve, getPrimeFactors(12));
23+
Assert.assertEquals(expectedPrimeFactorsMapForEighteen, getPrimeFactors(18));
24+
}
25+
26+
@Test
27+
public void testLCM() {
28+
Assert.assertEquals(36, PrimeFactorizationAlgorithm.lcm(12, 18));
29+
}
30+
}

‎java-numbers-2/src/test/java/com/baeldung/lcm/SimpleAlgorithmUnitTest.java‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package com.baeldung.lcm;
2+
3+
import org.junit.Assert;
4+
import org.junit.Test;
5+
6+
import static com.baeldung.lcm.SimpleAlgorithm.*;
7+
8+
public class SimpleAlgorithmUnitTest {
9+
10+
@Test
11+
public void testLCM() {
12+
Assert.assertEquals(36, lcm(12, 18));
13+
}
14+
15+
}

0 commit comments

Comments
 (0)