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
Post a Comment
Write your comment here.