编程里怎么求最大公约数

在编程中，求两个数的最大公约数（GCD）有多种方法，其中最常用且高效的是 辗转相除法（也称为欧几里得算法）。以下是几种不同编程语言中求最大公约数的方法：

Python

使用内置的`math.gcd（）`函数：

```python

import math

def calculate_gcd（a, b）:

return math.gcd（a, b）

a = 36

b = 60

print（f"GCD（{a}, {b}） = {calculate_gcd（a, b）}"）

```

使用辗转相除法（欧几里得算法）：

```python

def calculate_gcd（a, b）:

while b:

a, b = b, a % b

return a

a = 36

b = 60

print（f"GCD（{a}, {b}） = {calculate_gcd（a, b）}"）

```

C语言

使用辗转相除法（欧几里得算法）：

```c

include

int gcd（int a, int b） {

while （b != 0） {

int temp = b；

b = a % b；

a = temp；

}

return a；

}

int main（） {

int num1, num2；

printf（"请输入两个正整数：\n"）；

scanf（"%d %d", &num1, &num2）；

int result = gcd（num1, num2）；

printf（"%d和%d的最大公约数是：%d\n", num1, num2, result）；

return 0；

}

```

Java

使用`BigInteger`类的`gcd（）`方法：

```java

import java.math.BigInteger；

public class Main {

public static void main（String[] args） {

BigInteger num1 = new BigInteger（"36"）；

BigInteger num2 = new BigInteger（"60"）；

BigInteger result = num1.gcd（num2）；

System.out.println（"GCD（" + num1 + ", " + num2 + "） = " + result）；

}

}

```

使用辗转相除法（欧几里得算法）：

```java

public class Main {

public static int gcd（int a, int b） {

while （b != 0） {

int temp = b；

b = a % b；

a = temp；

}

return a；

}

public static void main（String[] args） {

int num1 = 36；

int num2 = 60；

int result = gcd（num1, num2）；

System.out.println（"GCD（" + num1 + ", " + num2 + "） = " + result）；

}

}

```

C++

使用``库中的`std::gcd（）`函数（C++17及以上版本）：

```cpp

include

include

int main（） {

int num1 = 36, num2 = 60；

int result = std::gcd（num1, num2）；

std::cout << "GCD（" << num1 << ", " << num2 << "） = " << result << std::endl；

return 0；

}

```

使用辗转相除法（欧几里得算法）：

```cpp

include

int gcd（int a, int b） {

while （b != 0） {

int temp = b；

b = a % b；

a = temp；

}

return a；

}

int main（） {

int num1 = 36, num2 = 60；

int result = gcd（num1, num2）；

std::cout << "GCD（" << num1 << ", " << num2 << "） = " << result << std::endl；

return 0；

}

```

这些方法中，辗转相除法是最常用的，因为它的时间复杂度为O（log（min（a, b））），非常高效。其他方法如穷举