{"id":18474,"date":"2021-08-26T10:39:15","date_gmt":"2021-08-26T05:09:15","guid":{"rendered":"https:\/\/python-programs.com\/?p=18474"},"modified":"2021-11-22T18:37:16","modified_gmt":"2021-11-22T13:07:16","slug":"python-program-to-find-gcd-of-elements-in-a-given-range","status":"publish","type":"post","link":"https:\/\/python-programs.com\/python-program-to-find-gcd-of-elements-in-a-given-range\/","title":{"rendered":"Python Program to Find GCD of Elements in a Given Range"},"content":{"rendered":"

In the previous article, we have discussed Python Program to Sort digits of a Number in Ascending Order<\/a>
\nHighest Common Factor (HCF) \/ Greatest Common Divisor (GCD) :<\/strong><\/p>\n

When at least one of the integers is not zero, the greatest positive integer that evenly divides the numbers without a remainder is called the Highest Common Factor or Greatest Common Divisor.<\/p>\n

The GCD of 12 and 16 is, for example, 4.<\/p>\n

Given two numbers, n, and m, and the task is to solve the equation, Find the largest integer a(gcd) that is divisible by all integers n, n + 1, n + 2,…, m.<\/p>\n

We only need to look at two cases here:<\/p>\n

If a = b, the segment is made up of a single number, so the answer is a.
\nIf a = b, then gcd(n, n + 1, n?+ 2,…, m) = gcd(n, n + 1), n + 2,…, m) = gcd(1, n + 2,…, n) = 1.<\/p>\n

Examples:<\/strong><\/p>\n

Example1:<\/strong><\/p>\n

Input:<\/strong><\/p>\n

Given First Number =\u00a0  125\r\nGiven Second Number = 125<\/pre>\n

Output:<\/strong><\/p>\n

The greatest number that divides both 125 and 125 = 125<\/pre>\n

Example2:<\/strong><\/p>\n

Input:<\/strong><\/p>\n

Given First Number = 5\r\nGiven Second Number = 8<\/pre>\n

Output:<\/strong><\/p>\n

The greatest number that divides both 5 and 8 = 1<\/pre>\n

Program to Find GCD of Elements in a Given Range in Python.<\/h2>\n

Below are the ways to Find the largest integer a(gcd) that is divisible by all integers n, n + 1, n + 2,…, m.<\/p>\n