This post will tell you in detail about "Consecutive Integer checking method to find GCD of two numbers with an example"
This algorithm calculates the Greatest common divisor (GCD) of two input numbers. The steps are as follows,
To find GCD of two numbers m and n,
step 1: Assign the value of minimum of {m,n} to t.
step 2: Divide m by t. If the reminder of the division is zero, go to step 3. Otherwise go to step 4.
step 3: Divide n by t. If the reminder is zero, return the value of t as the answer and stop. Otherwise, proceed to step 4.
step 4: Decrease the value of t by ¡®1¡¯ and go to step 2.
Example:
Finding GCD of two 60 and 24:
= > GCD(60,24)
Iterations:
1.T = min{60,24) = 24.
Divide m=60 by T=24 and check the reminder.
60%24=12. (not zero), so decrease t by 1. Now T=23.
2.T = 23.
Divide m=60 by T=23 and check the reminder.
60%23=14. (not zero), so decrease T by 1. Now T=22.
3.T = 22.
Divide m=60 by T=22 and check the reminder.
60%22=16. (not zero), so decrease T by 1. Now T=21.
4.T = 21.
Divide m=60 by T=21 and check the reminder.
60%21=18. (not zero), so decrease T by 1. Now T=20.
5.T = 20.
Divide m=60 by T=20 and check the reminder.
60%20=0. (Zero, so divide n=24 by T=20),
24%20=4 (Not zero), so decrease T by 1. Now T=19.
And so on....
13.At 13th iteration, T=12.
Divide m=60 by T=12 and check the reminder.
60%12=0. (Zero, so divide n=24 by T=12),
24%12=0 (Zero), We got the GCD.
Return value of t as the answer.
The required GCD of 60 and 24 is 12.
I think this problem can answer the question "Explain Consecutive integer checking method algorithm" or "What is Consecutive integer checking algorithm". Mainly for VTU Students. :P
Tags: Consecutive Integer Checking, GCD of two numbers, ADA, DAA
Share your views about this article!