Algorithm
Problem link- https://www.spoj.com/problems/GDCOFTI/
GDCOFTI - Greatest Common Divisor Of Three Integers
It is said that the greatest common divisor (GCD) of two or more whole integers, is the largest integer that divides them without leaving residue. Euclid's algorithm is famous for allowing to find the GCD between two integers. This challenge asks you, you find the GCD between three integers.
Challenge
The entry consists of 3 whole nonnegative integers (< 264), one per line and the output will be the GCD of the 3 integers.
Example of input
426 132 120
Example of output for this input
6
Example of input:
100 60 120
Example of output for this input
20
Example of input:
4 8 12
Example of output for this input
4
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
def gcd(A, B):
if A == 0:
return B
return gcd(B % A, A)
result = 0
for i in range(3):
result = gcd(result, int(input()))
print(result)Input
132
120
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
typedef long long LL;
LL gcd(LL a, LL b)
{
if(a == 0 || b == 0)
return (a + b);
else
return gcd(max(a, b)%min(a, b), min(a, b));
}
int main()
{
LL a, b, c;
scanf("%lld %lld %lld", &a, &b, &c);
printf("%lld\n", gcd(gcd(a, b), c) );
return 0;
}Input
132
120
Output
Demonstration
SPOJ Solution-Greatest Common Divisor Of Three Integers-Solution in C, C++, Java, Python