GCD ExampleGCD is known as the greatest common divisor, or greatest common factor (gcf), and is the largest positive integer that divides into two numbers without a remainder. For example, the GCD of 9 and 15 is 3. GCD is used in many encryption algorithms. The results are then:
|
Try an example
- GCD(3,5) should give 1. GCD [Ref]
- GCD(12,60) should give 12. GCD [Ref]
- GCD(12,90) should give 6. GCD [Ref]
- GCD(12, 30) should give 6. GCD [Ref]
- GCD(42, 56) should give 14. GCD [Ref]
Sample code
static int GCD(int a, int b) { int rem; while( b != 0 ) { rem = a % b; a = b; b = rem; } return a; }
Python
The following gives an example of the equivalent Python code:
def gcd(a, b): while( b != 0 ): Remainder = a % b; a = b; b = Remainder; return a; g = gcd(54,8) print g