python如何求因数
原创Python在求因数方面非常灵活,但很多人可能不知道Python如何求因数,Python提供了许多内建函数和运算符,可以用来求因数。
我们可以使用Python的除法运算符(/)和取模运算符(%)来求两个数的最大公因数和最小公倍数。
def gcd(a, b): while b != 0: a, b = b, a % b return a def lcm(a, b): return (a * b) // gcd(a, b)
gcd()函数使用欧几里得算法,通过不断取模和除法,求出两个数的最大公因数。
lcm()`函数利用这样一个性质:两个数的乘积等于它们的最大公因数和最小公倍数的乘积,因此可以通过除以最大公因数得到最小公倍数。
我们还可以使用素因数分解来求一个数的所有素因数,Python的math
模块提供了isqrt()
函数,可以用来求一个数的平方根内的所有因数,我们可以遍历这些因数,把它们加入到一个列表中,最后返回这个列表。
import math def prime_factors(n): i = 2 factors = [] while i * i <= n: if n % i == 0: factors.append(i) n //= i else: i += 1 if n > 1: factors.append(n) return factors
在这个函数中,我们首先让i
等于2,然后不断让i
加1,同时判断n
是否能被i
整除,如果能被整除,我们就把i
加入到factors
列表中,并把n
除以i
;如果不能被整除,我们就让i
加1,如果n
大于1,我们就把n
加入到factors
列表中,这个函数返回的factors
列表就是n
的所有素因数分解。
上一篇:如何加密python代码 下一篇:python如何装插件