Medium Problems on GCD and LCM
- Basic and Extended Euclidean algorithms
- Program to find GCD of floating point numbers
- HCF of array of fractions (or rational numbers)
- Pair with maximum GCD from two arrays
- LCM of factorial and its neighbors
- Largest subarray with GCD one
- Replace every matrix element with maximum of GCD of row or column
- Check if LCM of array elements is divisible by a prime number or not
- Print the kth common factor of two numbers
- Finding LCM of more than two (or array) numbers without using GCD
- Given GCD G and LCM L, find number of possible pairs (a, b)
- GCD of two numbers formed by n repeating x and y times
- Largest Subset with GCD 1
- Count pairs of natural numbers with GCD equal to given number
Mathematical Algorithms | GCD & LCM
Greatest Common Divisor (GCD):
The GCD of two numbers is defined as the largest integer that divides both integers without any remainder. It is also termed as the HCF (Highest Common Factor). GCD of an array is the integer that divides all the elements of the array without leaving any remainder.
GCD of two numbers may be calculated using the following ways:
- Prime Factorization
- Divisions by Prime
- Euclidean Algorithm
Least Common Multiple (LCM):
The LCM of two numbers is defined as the smallest integer which is a multiple of both integers. LCM of an array is the smallest possible integer that is multiple of all the elements of the array.
Below are some process to find LCm of two numbers:
- Prime Factorization
- Divisions by Prime
- Using the relation between GCD and LCM
Relation between GCD and LCM:
Consider two integers a and b and their GCD be gcd(a, b) and LCM be lcm(a, b) . Therefore,
a * b = gcd(a, b) * lcm(a, b)