本文实例讲述了Python实现利用最大公约数求三个正整数的最小公倍数。分享给大家供大家参考，具体如下：
在求解两个数的小公倍数的方法时，假设两个正整数分别为a、b的最小公倍数为d，最大公约数为c。存在这样的关系d=a*b/c。通过这个关系式，我们可以快速的求出三个正整数的最小公倍数。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
def divisor(a,b): c = a%b while c>0: a=b b=c c=a%b return bx1 = input("input1:")x2 = input("input2:")x3 = input("input3:")x0 = x1*x2/divisor(x1,x2)x0 = x0*x3/divisor(x0,x3)print "the least multiple is:%d"%x0 |
通过函数divisor求解两个数的最大公约数，然后进行两次求解最小公倍数即可知道三个正整数x1、x2、x3的最小公倍数。
其实可以通过divisor1函数求两个数的最小公倍数，再进行嵌套调用实现三个数的最小公倍数。
divisor1函数如下：
|
1
2
3
4
5
6
7
8
9
|
def divisor1(a,b): a1 = a b1 = b c = a%b while c>0: a=b b=c c=a%b return a1*b1/b |
嵌套过程如下：
|
1
|
x0 = divisor1(divisor1(x1,x2),x3) |
可以求得三个正整数的最小公倍数。
Tip: a-bx=c，可知当一个数为a、b的公约数时，同时也是c的约数。
通过最大公约数即可得到最小公倍数的求解。
|
1
2
|
def min_multi(a,b): return a*b/divisor1(a,b) |
求解质数的函数：
|
1
2
3
4
5
|
def isPrime(n): for i in range(2,int(n**0.5)+1): if n%i==0: return False return True |
希望本文所述对大家Python程序设计有所帮助。
原文链接：http://blog.csdn.net/qq_15508113/article/details/51493257
