HCF and LCM
Finding the HCF and LCM of a set of numbers is something we all have done in mathematics during school days, and we have to do it in college and as professionals. The reason is questions related to HCF and LCM are asked in the Aptitude round of Companies.
The aptitude test eliminates the students who score less than cut-off marks, so it is essential to ace the Aptitude test.
If you are looking for Aptitude preparation, you must check out the Aptitude Preparation Guided Path on CodeStudio, where all the necessary domains in Aptitude are covered in-depth.
This blog will discuss HCF and LCM in detail.
The greatest number which divides each of the two or more numbers is called HCF or Highest Common Factor. It is also called the Greatest Common Measure(GCM) and Greatest Common Divisor(GCD).
Before moving on to finding HCF, let's first look at a question related to it.
Three big drums contain 36 litres, 45 litres, and 72 litres of oil. What is the biggest measure which can measure all the different quantities exactly?
In an examination, if you find such a question where the biggest/largest/maximum measurement is desired, you should be clear that you need to find HCF.
So in the above question, you need to find the HCF of 36, 45, and 72. But wait, do we know how to find HCF?
Read further to know the three different techniques commonly used to find HCF. We will also look at a few of the important questions.
How to find HCF
There are three ways to find HCF:
By Prime Factorization Method
Remember in school days, we wrote down the prime factors of the given numbers, found the common factors, and then multiplied them. The method we used then was Prime Factorization. To quickly revise what we used to do then, let's look at the steps of finding HCF by prime factorization.
i) Write down the prime factors of the given numbers.
ii) Write down the prime factors which are common to both.
Iii) And products of the common factors will give you HCF of the numbers
Let's take an example to remember what we did in school days; you are required to find HCF of 150 and 375.
Step 1: Write down the prime factors of the given numbers.
150 = 2 × 3 × 5 × 5
375 = 3 × 5 × 5 × 5
Step 2: Write down the prime factors which are common to 150 & 375.
They are 3,5 & 5.
Step 3: Products of the common factors are 3 × 5 × 5
Hence, HCF = 75.
How about finding HCF of more than two numbers? Let's take four numbers like 10, 100, 150, and 50, respectively. As a first step, you need to list down the prime factors of each of the numbers. (Remember that you are to list the prime factors, so if the number is 160, you cannot write it as 4*40, as 4 and 40 both are composite numbers. You will write it as 2^5 * 5.)
10 = 2 * 5
100 = 2^2 * 5^2
150 = 2 * 3 * 5^2
50 = 2 * 5^2
HCF (a,b,c,d) →All common prime factors with their lowest available power.
HCF of a, b, c, and d will be
HCF = 2 * 5.= 10.
We cannot include 3 in our calculation as 3 is not common in all the available numbers.
By Division Method
If we were given two numbers, then.
● First, divide the large number by a small number.
● If the remainder is left, then divide the first divisor by remainder.
● If the remainder divides the first divisor completely, then it is the highest common factor of the given two numbers.
● If the remainder does not divide the first divisor completely, then repeat the steps.
Let's take an example where we are required to find HCF of 120 and 100.
Step 1) First, divide the larger number, i.e., 120, by the smaller number, i.e., 100
120/100 -> 1 and remainder is 20.
Step 2) Divide the first divisor, i.e., 100, by the remainder 20.
100/20 -> 5 and remainder is 0.
The HCF is 20.
What do you think is it possible to find HCF of more than two numbers using the division method?
If your answer is Yes, then you are correct.
Follow the below steps to find the HCF of three numbers using the division method:
- First of all, find the highest common factor (H.C.F) of any two of the given numbers.
- Now find the highest common factor (H.C.F) of the third given number and the highest common factor (H.C.F) obtained in Step 1 from the first and the second number.
Find the HCF of 184, 230, and 276 using the division method.
Step 1) Find the HCF of 184 and 230.
Now that you know the division method for finding the HCF of two numbers find it yourself.
The HCF is 46.
Step 2) Find the HCF of 276 and 46.
Again it is 46.
Therefore the HCF of 184, 230, and 276 is 46.
By Shortcut Method
The two methods discussed above are quite efficient but sometimes can be slow enough. When we are dealing with questions related to HCF in an examination, the average time one gets for each question is close to 50-60 seconds.
The shortcut method revolves around the concept that “When you talk about the common factor of two numbers X & Y., then the common factor has to leave the same remainder 0.
This means ``Let two numbers X & X+12, the only numbers that will have the possibility of leaving the same remainder zero would be factors of 12."
When you talk about the common factor of two numbers X & Y., then the common factor has to leave the same remainder, "zero." This means Let two numbers X & X+12, the only numbers that will have the possibility of leaving the same remainder zero would be factors of 12.
Let’s look at an example wherein we are required to find the HCF of 38 and 50.
50-38 = 12, factors of 12 are 12, 6, 4, 3, 2 and 1.
12-> Do not divide 38. So this cannot be the HCF
6-> Do not divide 38
4-> Do not divide 38.
3->Do not divide 38.
2-> Divide 38.
The HCF is 2.
Let's take another example, wherein you need to find the HCF of 34 and 70.
70-34 = 36.
Factors of 36 are 36, 12, 9, 6, 4, 3 and 2.
36-> Do not divide 34.
12-> Do not divide 34.
Similarly, 9, 6, 4, and 3 do not divide 34.
The HCF will be 2.
We just covered three methods related to finding HCF. Now it's time to practice more and more questions related to finding HCF.
The least common Multiple(LCM) is a method to find the smallest common multiple
between two or more numbers. A common multiple is a number which is a multiple
of two or more numbers.
Let's look at various methods for finding LCM.
How to find LCM
There are two main methods for finding LCM of a set of numbers:
By Prime Factorization
Step1: Find the prime factor of two numbers, a & b.
Step2: Write down all the prime factors that appear at least once in the numbers a & b.
Step3: Write all the prime factors with their highest power.
Step4: Products of all the prime factors with their highest power will give you LCM of a & b.
Let's take a look at an example of finding LCM of two numbers, 12 and 80.
Step 1: List the prime factors of 12 and 80
12 = 2 * 2 * 3
80 = 2 * 2 * 2 * 2 * 5
Step2: Write down all the prime factors that appear, at least once in the numbers:
Step3: Write all the prime factors with their highest power: 2^4 × 3^1 × 5^1
Step4: The LCM = 2^4 × 3^1 × 5^1 = 240
Similarly, you can find LCM of more than two numbers, 30, 40, 50, 60, and 70.
Step 1) List the prime factors of 30, 40, 50, 60, and 70.
30 = 2 * 3 * 5
40 = 2 * 2 * 2 * 5
50 = 2 * 5 * 5
60 = 2 * 2 * 3 * 5
70 = 2 * 5 * 7
Step 2) Write down all the prime factors that appear, at least once in the numbers:
Step 3) Write all the prime factors with their highest power: 2^3 * 3^1 * 5 ^2 * 7^1.
Step 4) Find the LCM, 2^3 * 3^1 * 5 ^2 * 7^1 = 4200.
As you saw, LCM is the product of the highest power of all the prime factors, but that process would be very tedious, especially when the numbers are small. The below method will demonstrate finding LCM of smaller numbers.
By Shortcut Method
When the numbers are small, the logic of LCM builds around the Coprime numbers.
Co-prime Number: Two numbers are Coprime to each other when they have no common factor.
For example: (6, 13), (7, 11), (9, 19) etc.
Three numbers are Coprime to each other when pairwise; each pair is Co-prime. For example, Three numbers be a,b and c are Coprime when,
a,b are Coprime,
a,c are Coprime,
& b,c are Co-prime.
All three pairs should be Coprime to each other; only then, a, b and c will be Co-prime.
NOTE: When a & b is Co-prime, then the HCF should be 1.
Some important points about the Coprime numbers:
(i) Two consecutive natural numbers are always coprime (Example 5, 6; 82, 83; 749, 750, etc.)
(ii) Two consecutive odd numbers are always coprime (Examples: 7, 9; 51, 53; 513, 515, etc.)
(iii) Two prime numbers are always coprime (Examples: 13, 17; 53, 71, and so on).
(iv) One prime number and another composite number (such that the composite number is not a multiple of the prime number) are always coprime (Examples: 17, 38; 23, 49, and so on, but note that 17 and 51 are not coprime, as 51.
Shortcut for LCM
When the numbers are coprime, then LCM is their product. So, 7, 9, and 11 are coprime; The LCM is 7 × 9 × 11.
What to do when you have a mix of prime and coprime numbers?
In that case, you need to take care of the following two points:
(i). LCM has to be the multiple of HCF.
(ii). For any two numbers a & b, Product of two numbers (𝑎 × 𝑏) = 𝐿𝐶𝑀 × 𝐻𝐶𝐹 (this formula is valid for two numbers)
Let's take an easy example to understand the shortcut method for finding the LCM of four numbers, say 42, 44, 18, and 25.
Step 1) Find the pair of coprime numbers and note it down, 18 and 25 are coprime to each other, 25 and 42 are also coprime, 25 and 44 are also coprime.
For the below example, we are taking 18 and 25 as the pair of coprime numbers.
Step 2) LCM starts with 18 * 25 …
Step 3) Now, the logic of LCM should contain all the other numbers from the given numbers. Out of the LCM, you should be able to construct 42 and 44 also.
Step 4) The factor of 42= 2 × 3 × 7. Inside 18, you have 2 & 3, But you don't have 7 in 25 and 18. To construct 42, you should have a 7 in your LCM. ( LCM=18 × 25 × 7....)
Step 5) The factor of 44= 2 × 2 × 11. Inside 18, you have one 2, but there are no 11 and the other 2 in this LCM; so, to construct 44, you need to introduce 2 & 11 into the LCM. So, LCM will be = 18 × 25 × 7 × 2 × 11.
The above method is quite intuitive, and you can easily find the LCM using this method once you have practised enough questions using this method.
We just covered two methods related to finding LCM. Now it's time to practice more and more questions related to finding LCM.
Let's look at a question related to HCF and LCM commonly asked in the Aptitude round, the product of two numbers is 2028, and their HCF is 13; the number of such pairs is:
Solution: Product of two numbers = 2028
HCF = 13
Let the numbers be 13a and 13b. Then 13a * 13b = 2028
That means, ab = 2028/13 * 13 = 12
Now the coprimes with product 12 are (1, 12) and (3, 4).
So, the required numbers are (13*1, 13*12) and (13*3, 13*4)
There are two such pairs.
Frequently Asked Questions
Q1) What are HCF and LCM?
Ans 1) HCF: The greatest number that divides each of the two or more numbers is HCF or Highest Common Factor. It is also called the Greatest Common Measure(GCM) and Greatest Common Divisor(GCD).
LCM: Least Common Multiple(LCM) is a method to find the smallest common multiple between any two or more numbers. A common multiple is a number which is a multiple of two or more numbers.
Q2) How to find the HCF of two numbers?
Ans 2) HCF of two numbers can be found using either of the following methods:
- By Prime Factorization Method.
- By division method
- By shortcut method
This blog discussed how to find HCF and LCM in detail. With this done, you may now switch towards aptitude preparation from our Guided Path.
A common problem faced by all of us is that we prepare well, but during online assessments, we cannot solve the questions on time. To overcome this, Coding Ninjas have come up with an online mock test series. The mock tests for leading companies like Amazon, Microsoft, Google, Adobe, Flipkart, TCS, Wipro, and Accenture are free. Our team of experts has curated and designed these online mock test series to help you prepare better for your coding interview rounds. In this online test series, you will get multiple tests that include the latest coding interview questions. Start preparing for the 2021 Amazon, Microsoft, etc., tech interviews now.