Compute the greatest common divisor (GCD) of two positive integers — the largest number that divides both.
Input
A single line with two positive integers a and b.
Output
The greatest common divisor of a and b.
Greatest Common Divisor
Easymathnumber-theory
Examples
Example 1
- Input
12 18
- Output
6
6 divides both 12 and 18, and nothing larger does.
Example 2
- Input
17 5
- Output
1
17 and 5 share only 1.
Example 3
- Input
100 100
- Output
100
The GCD of a number with itself is the number.
Constraints
- 1 <= a, b <= 10^9
Hints
Reveal hint 1
Euclid's algorithm: gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = a.
Reveal hint 2
Repeatedly replace (a, b) with (b, a mod b) until b becomes 0.
Reference solution (spoiler — try it yourself first)
Approach
Euclid's algorithm: while b is non-zero, replace (a, b) with (b, a mod b); the answer is a.
import math
a, b = map(int, input().split())
print(math.gcd(a, b))
Bring us the problem, not a perfect specification
Tell us what needs to change, who it affects and any important deadline. We will review the context and reply with useful next questions.
- 01Share contextDescribe the workflow, constraint or risk.
- 02Clarify togetherWe identify missing facts and useful options.
- 03Choose a startAgree a focused assessment or delivery step.