 using prime factors.
What is LCM?
LCM (Least Common Multiple) of two numbers is smallest number that is divisible by both.
For Example,
LCM of 90 and 120 is 360
Explanation:
360 / 90 = 4 360 / 120 = 3
We can find LCM using below ways –
In this post, we learn to find LCM using prime factors.
1. Program to Find LCM of Two Numbers (Using Prime Factors)
We can find lcm (least common multiple) of two numbers using Prime Factorisation.
Pseudo Algorithm
- Find prime factors of a and b in array aFactors and bFactors.
- Calculate union of both prime factors
- Multiply that factors to get lcm
import java.util.* import kotlin.collections.HashMap import kotlin.math.sqrt fun main() { val scanner = Scanner(System.`in`) println("Enter a:") val a = scanner.nextInt() println("Enter b:") val b = scanner.nextInt() val aFactors = primeFactors(a) val bFactors = primeFactors(b) var lcm = if (aFactors.size > 0 && bFactors.size > 0) 1 else 0 // Compare factors of a and b. for (mapEntry in aFactors) { val aCount = mapEntry.value val bCount = bFactors[mapEntry.key] if (bCount != null) { // If factors of a are present in b. // Find maximum count of factors in a and b. val maxCount = if (bCount > aCount) bCount else aCount // Multiply key up-to maxCount times with lcm. for (index in 1..maxCount) lcm *= mapEntry.key } else { // If factors of a are not present in b. for (index in 1..aCount) lcm *= mapEntry.key } } // If factors of b are not present in a. for (mapEntry in bFactors) { val bCount = mapEntry.value val aCount = aFactors[mapEntry.key] if (aCount == null) { for (index in 1..bCount) lcm *= mapEntry.key } } println("LCM of $a and $b: $lcm") } private fun primeFactors(number: Int): HashMap<Int, Int> { // Hash map that contains all the prime factors of given number. val map: HashMap<Int, Int> = HashMap() var n = number if (n <= 0) { return map } // At first check for divisibility by 2. // Add it in arr till it is divisible var count = 1 while ((n % 2) == 0) { map[2] = count count++ n /= 2 } val squareRoot = sqrt(n.toDouble()).toInt() // Run loop from 3 to square root of n. // Check for divisibility by i. // Add i in map till it is divisible by i. for (i in 3..squareRoot step 2) { count = 1 while (n % i == 0) { map[i] = count count++ n /= i } } // If n is a prime number greater than 2. if (n > 2) { count = 1 map[n] = count } return map }
When you run the program, output will be –
Enter a: 120 Enter b: 200 LCM of 120 and 200: 600
Explanation:.
Here, we find factors of a and store it in aFactors.
Then, we find factors of b and store it in bFactors.
Then, we find union of both array aFactors and bFactors
There are three scenarios –
- Factors of a are present in b.: Find maximum count (i.e. maxCount) of occurrence. Then, run a loop and multiply that factor up-to maxCount times.
- Factors of a are not present in b.: Then, run a loop and multiply that factor up-to aCount times.
- Factors of b are not present in a.: Then, run a loop and multiply that factor up-to bCount times.
Finally, we get lcm of a and b.
Thus, we went through Kotlin Program to find LCM using prime Factors of two numbers.