[Algorithm] - Middle school procedure to find GCD of two numbers, with an example

This post will tell you in detail about "Middle school procedure to find GCD of two numbers with an example"



This algorithm calculates the Greatest common divisor (GCD) of two input numbers. This algorithm works on the basis of common divisors of the two input numbers. The steps are as follows,

To find GCD of two numbers m and n,
step 1: Find the prime factors of m. Go to step 2.
step 2: Find the prime factors of n. Go to step 3.
step 3: Identify all the common factors between m and n. proceed to step 4.
step 4: Compute the product of all the common divisors of the two numbers. and the product is the required GCD.


Example:
Finding GCD of two 60 and 24:
= > GCD(60,24)

Write 60 in terms of product of its prime factors,
=> 60 = 2 x 2 x 3 x 5

Write 24 in terms of product of its prime factors,
=> 24 = 2 x 2 x 2 x 3

Find the common occurrence of the prime factors in both the numbers
common numbers are = 2 , 2 , 3 .

Therefore,
GCD = Product (2 , 2 , 3) = 12

The required GCD of 60 and 24 is 12.


I think this problem can answer the question "Explain Middle school procedure to find GCD of two numbers" or "What is Middle school procedure algorithm". Mainly for VTU Students. :P


Tags: GCD of two numbers using middle school procedure,Middle school procedure,ADA,DAA

Author : Anonymous

He is a simple passionate tech freak who himself is an engineering student at Canara Engineering college. He likes App Development, Web designing, Blogging, Youtubing, Debugging and also is a CodeGeek!

Sharing is sexy!

Related Articles