GCD of Two Numbers

Practice this coding question on Coding Gurukul.

Problem statement

Two ribbon rolls must be cut into equal whole-number lengths without leaving scraps. Find the largest piece length that works for both rolls. Your task Compute the greatest common divisor of the positive integers a and b. Important details The answer must divide both values exactly. It is the largest such positive divisor, not the smallest common multiple. Equal lengths have that length as their answer; coprime lengths have answer one. Apply the Euclidean algorithm, repeatedly reducing a pair with a remainder, to handle large inputs efficiently. Swapping the order of the two input lengths must not change the result. Worked example For lengths 48 and 18, pieces of length 6 divide both rolls. No larger length does, so print 6.

Input format

One line contains a and b.

Output format

Print gcd(a, b).

Constraints

1 <= a, b <= 1000000000.

Sample input

48 18

Sample output

6

Sign in to run or submit a solution in C++, Java or Python.