137. GCD

Find the Greatest Common Divisor of n numbers.

Input. The first line contains the value of n (1 < n < 101). The second line contains n positive integers. Each number is not greater than 30000.

Output. Print the Greatest Common Divisor of n numbers.

Sample input	Sample output
2 15 25	5

SOLUTION

GCD

Algorithm analysis

It is known that

GCD (a₁, a₂, …, a_i) = GCD (GCD (a₁, a₂, …, a_{i - 1}) , a_i)

We shall sequentially calculate the greatest common divisor of two, three,…, n numbers. For example, for four numbers holds an equality:

GCD (a₁, a₂, a₃, a₄) = GCD (GCD (GCD (GCD (0, a₁), a₂), a₃), a₄)

Algorithm realization

Function gcd finds the Greatest Common Divisor.

int gcd(int a, int b)

{

return (!b) ? a : gcd(b, a % b);

}

Read the input data and sequentially find GCD of n numbers.

res = 0;

scanf("%d", &n);

while (n--)

{

scanf("%d", &b);

res = gcd(res, b);

}

Print the answer.

printf("%d\n", res);