Friday, October 4, 2013

Algorithm to find GCD (Greatest common divisor )

What is GCD ?
 The largest integer that divides a set of numbers

Eg . GCD for 15 and 10 is 5

To find this prophetically Eucilds algorithm can be used. it is very much easy and fast way to find GCD within the programs.

Algorithm :
assume "a" and "b" are the numbers we need to find GCD

A=a and B=b
while B>0 do
         R= A mod B
         A = B
         B = R
return A

Following python code shows how it can be used in a python program  
#Find GCD with Eucilds Algorithm
def FindGCD_Eucilds(num_one,num_two):
    A=num_one
    B=num_two
    while (B>0):
        R=A%B
        A=B
        B=R
    return A

print(FindGCD_Eucilds(15,5))

No comments:

Post a Comment