GCD of N numbers

Back to Programming

Description

GCD stands for Greatest Common Divisor. The program is written here to find the GCD of ‘n’ numbers. The number of elements and the numbers of which the GCD is to be found are taken as input. For example, let the number of elements be 3 and the numbers are 12, 15 and 18. First, the first pair of numbers is 12 and 15, whose GCD is 3, now; the GCD of 3 and 18 will be found which is also 3. Therefore, the GCD of 12, 15 and 18 is 3.

Algorithm

INPUT: The number of elements and the elements of which the GCD is to be calculated.

OUTPUT: The GCD of the numbers

PROCESS:

Step 1: [Taking the input]

For i=0 to n-1 repeat

[End of ‘for’ loop]

Step 2: [Function to find the ‘gcd’ of two numbers stored in variables ‘x’ and ‘y’]

While x≠y repeat

If x>y then

Set x<-x-y

Else

Set y<-y-x

[End of ‘if-else’]

[End of ‘while’ loop]

[End of the function]

Step 3: [Finding the GCD]

Set g<-a[0]

For i=1 to n-1 repeat

Set g<-call the function ‘gcd(g,a[i])’

[End of ‘for’ loop]

[Printing the gcd]

Print "The GCD is: g"

[End of finding the GCD]

Step 4: Stop.

TIME COMPLEXITY:

for (i=1;i<n;i++)------------------------O(n)

g=gcd(g,a[i]);

The time complexity of this program is O(n) where ‘n’ is the number of elements of which the GCD is to be calculated.

SPACE COMPLEXITY:

The space complexity of this program is O(1) as it requires a constant number of memory spaces for any given input.