输入两个正整数m和n 求其最大公约数和最下公倍数
时间: 2023-11-25 22:48:54 浏览: 187
最大公约数(Greatest Common Divisor,简称GCD)和最小公倍数(Least Common Multiple,简称LCM)是两个正整数的常见数学概念。它们的定义如下:
- 最大公约数:两个数中能够同时整除它们的最大正整数。
- 最小公倍数:两个数的公共倍数中最小的一个正整数。
求两个正整数m和n的最大公约数和最小公倍数的方法有很多种,以下是其中两种常见的方法:
方法一:辗转相除法
辗转相除法,也称欧几里得算法,是求两个正整数最大公约数的一种常用方法。其基本思想是:用较大的数除以较小的数,再用余数去除较小的数,如此反复,直到余数为0为止。此时,较小的数就是这两个数的最大公约数。
最小公倍数可以通过最大公约数求得,公式为:两数的积除以它们的最大公约数。
以下是使用Python实现辗转相除法的代码:
```python
def gcd(m, n):
while n != 0:
m, n = n, m % n
return m
def lcm(m, n):
return m * n // gcd(m, n)
```
方法二:质因数分解法
质因数分解法是求两个正整数最大公约数和最小公倍数的另一种常用方法。其基本思想是:将两个数分别分解质因数,然后将它们的公共质因数乘起来得到它们的最大公约数,将它们的所有质因数乘起来得到它们的最小公倍数。
以下是使用Python实现质因数分解法的代码:
```python
def gcd(m, n):
factors_m = prime_factors(m)
factors_n = prime_factors(n)
common_factors = set(factors_m) & set(factors_n)
return prod(common_factors)
def lcm(m, n):
factors_m = prime_factors(m)
factors_n = prime_factors(n)
all_factors = set(factors_m) | set(factors_n)
return prod(all_factors)
def prime_factors(n):
i = 2
factors = []
while i * i <= n:
if n % i:
i += 1
else:
n //= i
factors.append(i)
if n > 1:
factors.append(n)
return factors
def prod(numbers):
result = 1
for number in numbers:
result *= number
return result
```
阅读全文