How to Find the GCD of N Integers Using Python

In this article, we will explore a Python program to calculate the Greatest Common Divisor (GCD) of N integers. The GCD of two or more integers is the largest positive integer that divides each of the numbers without leaving a remainder.

This program is particularly useful in mathematical computations and competitive programming. Let’s dive into the problem, input/output format, and solution.

Input and Output Format

Input:

1. The first line contains the integer N, representing the number of integers.
2. The second line contains N space-separated integers.

Output:

1. A single integer representing the GCD of the input numbers.

---

Example 1

Input:

5
4 6 2 8 16

Output:

2


Explanation:

• Divisors of 4: 1, 2, 4
• Divisors of 6: 1, 2, 3, 6
• Divisors of 2: 1, 2
• Divisors of 8: 1, 2, 4, 8
• Divisors of 16: 1, 2, 4, 8, 16

The common divisors are 1 and 2. The largest common divisor is 2, which is the output.

---

Example 2

Input:

2
8 12


Output:

4


Explanation:

• Divisors of 8: 1, 2, 4, 8
• Divisors of 12: 1, 2, 3, 4, 6, 12

The common divisors are 1, 2, and 4. The largest common divisor is 4, which is the output.

---

Python Code to Find GCD of N Integers

Here is the Python program to calculate the GCD of N integers:

from functools import reduce
from math import gcd

# Input the number of integers
n = int(input("Enter the number of integers (N): "))

# Input the list of integers
l = [int(i) for i in input("Enter the integers separated by space: ").split()]

# Calculate the GCD of the list using reduce and gcd
result = reduce(gcd, l)

# Print the result
print(f"The GCD of the given numbers is: {result}")

---

Step-by-Step Explanation of the Code

1. Import Required Libraries:
   • reduce from the functools module allows the application of a function cumulatively to the items in an iterable.
   • gcd from the math module calculates the GCD of two numbers.
2. Input Handling:
   • The first input (n) specifies the number of integers.
   • The second input is a space-separated list of integers stored in the list l.
3. GCD Calculation:
   • reduce(gcd, l) computes the GCD of all the integers in the list. It works by iteratively applying the gcd function:
     • First, it finds the GCD of the first two numbers.
     • Then, it uses the result to find the GCD with the next number, and so on.
4. Output the Result:
   • The calculated GCD is printed as the output.