Greatest Common Divisor

If you have two different numbers and also they are integers, let's say 6 and 3, we could easily the greatest common divisor is 3. Why?

1
2
6 = 3 x 2 x 1  
3 = 3 x 1

Both of 6 and 3 have same 1 and 3 as divisor. But the greatest one is 3. How about two big integers? it's hard to derived big integers into its prime numbers and see what number the greatest is. I developed a program in python named gcd. You can fork the program here. But I will give you the main idea of this program.

It said that,

1
2
gcd(a,0) = a  
gcd(a,b) = gcd(b, a mod b)

Let's say on previous example between 6 and 3.

1
gcd(6,3) = gcd(3,6 mod 3) = gcd(3,0) = 3

Aha! It's just the same with the previous result. Now let's go to the code!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
a = 30 # Change this as your first input, 30 is an example.  
b = 3098647 # Change this as your second input, 3098647 is an example.  
num1 = a  
num2 = b  
while b > 0:  
    q = a / b  
    r = a - q * b  
    a = b  
    b = r  
res = 'The GCD between ' + str(num1) + ' and ' + str(num2) + ' is ' + str(a)  
print res

Run the program and you will get the result.

Comments

Popular posts from this blog

Making SublimePythonIDE Works on Windows

How to Change Font Type in Sublime Text