HCF and LCM

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." 

1*12

2*6

3*4

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.

Practice a question asked in Sapient Hiring Drive 2018.

LCM

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: 

2,3,5.

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: 

2,3,5, 7.

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.

Practice Question asked in Infosys Hiring 2019

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

Key Takeaways

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. You can also consider our Aptitude Course to give your career an edge over others.