方法1:辗转相除法
有两整数a和b：
① a%b得余数c
② 若c=0，则b即为两数的最大公约数
③ 若c≠0，则a=b，b=c，再回去执行①
例如求24和9的最大公约数过程为：
24÷9 余6
9÷6余3
6÷3余0
因此，3即为最大公约数
#coding: utf-8n=int(raw_input('n='))
m=int(raw_input('m='))
a,b=n,m
p=0
temp=0
r=0if (n<m):
temp=n
n=m
m=temp
p=n*mwhile (m!=0):
r=n%m
n=m
m=rprint u'(%s,%s)最大公约数是: %s' % (str(a),str(b),str(n))print u'(%s,%s)最小公倍数是: %s' % (str(a),str(b),str(p/n))方法2：相减法
有两整数a和b：
① 若a>b，则a=a-b
② 若a<b，则b=b-a
③ 若a=b，则a（或b）即为两数的最大公约数
④ 若a≠b，则再回去执行①
例如求24和9的最大公约数过程为：
24－9＝15( 15>9 ) 15－9＝6( 9>6 )
9－6＝3( 6>3 ) 6－3＝3( 3==3 )
因此，3即为最大公约数
# coding: utf-8a=int(raw_input('a='))
b=int(raw_input('b='))
n=a
m=bwhile (a!=b): if a>b:
a=a-b else:
b=b-aprint u'(%s,%s)的最大公约数是: %s' % (n,m,a)print u'(%s,%s)的最小公倍数是: %s' % (n,m,m*n/a)方法3：穷举法
有两整数a和b：
① i=1
② 若a，b能同时被i整除，则t＝i
③ i++
④ 若 i <= a(或b)，则再回去执行②
⑤ 若 i > a(或b)，则t即为最大公约数，结束
改进的算法：
① i= a(或b)
② 若a，b能同时被i整除，则i即为最大公约数，结束
③ i--，再回去执行②
# coding: utf-8a=int(raw_input('a='))
b=int(raw_input('b='))
n=a
m=b
t=awhile (t>0): if (a % t == 0 and b % t == 0): break
t=t-1print u'(%s,%s)的最大公约数是: %s' % (n,m,t)print u'(%s,%s)的最小公倍数是: %s' % (n,m,m*n/t)