Problem C: 求最大公约数

Description

两个数能同时被一个数所整除，这个数就是公约数。例如，12和20的公约数有1，2，4。其中4是12和20的最大公约数。

Input

输入两个正整数，用逗号分隔。

Output

输出这两个数的最大公约数。

Method

可以用辗转相除法（欧几里得算法）或穷举法求最大公约数。辗转相除法的时间复杂度较低，适合较大的数值。

Using Euclidean Algorithm

步骤如下：

1. 设较大的数为a，较小的数为b。2. 计算a除以b的余数r。3. 设a = b，b = r，重复步骤2，直到b为0。4. 最后，a就是最大公约数。

示例：

计算24和60的最大公约数：

- 60 ÷ 24 = 2余12 → a=24, b=12- 24 ÷ 12 = 2余0 → 最大公约数为12。

Using Brute Force Method

步骤如下：

1. 对第一个数n，找出所有约数。2. 对第二个数m，找出所有约数。3. 比较两个数组，找出共同的约数，最大的那个即为最大公约数。

示例：

计算24和60的最大公约数：

- 24的约数：1, 2, 3, 4, 6, 8, 12, 24。- 60的约数：1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60。- 公约数：1, 2, 3, 4, 6, 12 → 最大为12。

Code Implementations

使用C语言实现欧几里得算法：

#include 
   
    int gcd(int a, int b) {    while (b != 0) {        int temp = a % b;        a = b;        b = temp;    }    return a;}int main() {    int n, m;    scanf("%d, %d", &n, &m);    int a, b;    if (n > m) {        a = n;        b = m;    } else {        a = m;        b = n;    }    printf("%d", gcd(a, b));}

或者使用Python：

def gcd(a, b):    while b != 0:        a, b = b, a % b    return an, m = map(int, input().split())print(gcd(n, m))

总结：

通过欧几里得算法，我们可以高效地计算两个数的最大公约数。这种方法的时间复杂度是O(log min(a, b))，非常适合处理较大的数。而穷举法虽然简单，但在数较大的情况下效率较低。因此，辗转相除法是更优的选择。

转载地址：http://rsux.baihongyu.com/

你可能感兴趣的文章