Greatest Common Divisor
It looks like none of beginner's courses on programming avoids practicing Euclid's algorithm for calculation of the greatest common divisor of two numbers.
Greatest Common Divisor or GCD of
b is such an integer value
c that both of
b are divisible by it
(e.g. leave no remainder) - and also
c is the largest possible. For example
gcd(20, 35) = 5 and
gcd(13, 28) = 1.
Euclid's algorithm is quite simple - we keep on subtracting smaller value (of
b) from larger - and repeat
this operation until values become equal - this last value will be
gcd. For speeding up the process we can use
modulo operation instead of subtraction.
20 35 - subtract first from second 20 15 - subtract second from first 5 15 - now subtract first from second twice 5 5 - and here is GCD
Least Common Multiple (or LCM) of
b is such an integer
d that it is divisible by both of them (and is
the smallest of all possible). It can be found with the following rule:
lcm(a, b) = a * b / gcd(a, b)
Input data contain number of test-cases in the first line.
Then lines with test-cases follow, each containing two numbers - for
Answer should contain GCD and LCM for each pair, surrounded by brackets and separated by spaces, for example:
input data: 2 2 3 4 10 answer: (1 6) (2 20)