To solve problem 11417 (GCD), it would be beneficial if one knows about the Euclidean algorithm and division algorithm. One could search up "greatest common divisor" in Google and browse through the corresponding Wikipedia article.

The algorithm to get the greatest common divisor between two numbers i and j can be best explained through an example. Consider i = 18 and j = 84, to get the GCD:

84 / 18 = 4 R 12

18 / 12 = 1 R 6

12 / 6 = 2 R 0

GCD for 18 and 84 is then 6.

Another example: i = 16 and j = 56:

56 / 16 = 3 R 8

16 / 8 = 2 R 0

GCD for 16 and 56 is then 8.

In the process illustrated above, the divisor that caused the remainder to be 0 is the greatest common divisor.

## No comments:

## Post a Comment