#2116. 找出两个数的所有公约数
找出两个数的所有公约数
找出两个数的所有公约数
题目描述:
给定两个整数 a 和 b,找出它们的所有公约数,并按升序输出。
输入:
两个整数 a 和 b(1 ≤ a, b ≤ 10^9)。
输出: 输出两个数的所有公约数,升序排列,结果用空格分隔。
测试数据:
- 输入:
12 18输出:1 2 3 6 - 输入:
28 35输出:1 7 - 输入:
20 30输出:1 2 5 10 - 输入:
45 60输出:1 3 5 15 - 输入:
48 64输出:1 2 3 4 6 8 12 16
解题思路:
- 计算
gcd(a, b)。 - 找出
gcd(a, b)的所有公约数。