Algorithm and Flowchart to Find GCD of Two numbers

[69207 views]

What is GCD?

GCD stands for Greatest Common Divisor. So GCD of 2 numbers is nothing but the largest number that divides both of them.
Example: Lets say 2 numbers are 36 and 60. Then
36 = 2*2*3*3
60 = 2*2*3*5
GCD=2*2*3
i.e GCD=12

GCD is also known as HCF (Highest Common Factor)

Algorithm for Finding GCD of 2 numbers:

Step 1: Start Step 2: Declare variable n1, n2, gcd=1, i=1 Step 3: Input n1 and n2 Step 4: Repeat until i<=n1 and i<=n2 Step 4.1: If n1%i==0 && n2%i==0: Step 4.2: gcd = i Step 5: Print gcd Step 6: Stop