Back to course home
0% completed
Vote For New Content
3. Greatest Common Divisor (GCD)
Problem Statement
Write recursive code to calculate the Greatest Common Divisor (GCD) of Two Positive Numbers.
The greatest common divisor (GCD) of two positive integers A and B is the largest positive integer that divides both A and B without leaving a remainder.
Let's see some example inputs/outputs for this example:
Input(s) | Output(s) | Explanation |
---|---|---|
A = 12, B = 18 | GCD = 6 | The factors of 12 are [1, 2, 3, 4, 6, 12], and the factors of 18 are [1, 2, 3, 6, 9, 18]. The common factors between 12 and 18 are [1, 2, 3, 6], and the largest common factor is 6. |
A = 25, B = 15 | GCD = 5 | The factors of 25 are [1, 5, 25], and the factors of 15 are [1, 3, 5, 15]. The common factors between 25 and 15 are [1, 5], and the largest common factor is 5. |
A = 40, B = 60 | GCD = 20 | The factors of 40 are [1, 2, 4, 5, 8, 10, 20, 40], and the factors of 60 are [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]. The common factors between 40 and 60 are [1, 2, 4, 5, 10, 20], and the largest common factor is 20. |
Try it yourself
Try solving this question here:
Code
Here is the code for this algorithm:
Python3
Python3
. . . .
.....
.....
.....
Like the course? Get enrolled and start learning!
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible