転がり相除法は最大公約数、最小公倍数を求める.

大学院受験の后、自分は突然机械の学习に兴味を持って、だからpythonの言语を独学して、自分のpythonの旅を始めて、自分は今まだ菜鸟で、自分がカタツムリのように、着実に前進することができることを望みます!今日はpython言語に基づいて、いくつかの方法で最大公約数、最小公倍数を求めます.まず、転がり相除算法の概念を紹介する2数をa,b(a>b)とし、gcd(a,b)でa,bの最大公約数を表し、r=a(mod b)はaをbで割った余り、kはaをbで割った商、すなわちa÷b=k......である.r.転がり相除去法はgcd(a,b)=gcd(b,r)を証明することである.第一歩:c=gcd(a,b)とするとa=mc,b=nc第二歩:前提からr=a-kb=mc-knc=( m-kn)c第三歩:第二歩の結果からcもrの因数第四歩:m-knとnの互質(m-kn=xd,n=yd(d>1)を仮定するとm=kn+xd=kyd+xd=(ky+x)d,a=mc=(ky+x)cd,b=nc= ycd,aとbの1つの公公d=kn+xd=kn+xd=kyd=kyd+xd=(ky+x)d,a=mc=(ky+x)cd約数cd>cであるため、cはaとbの最大公約数ではなく、前述の結論と矛盾する)ため,cもbとrの最大公約数である.従って、gcd(b,r)=c、次いでgcd(a,b)=gcd(b,r)であることが分かる.証明書はここにリンク内容を書きます.
質問:2つの正の整数を入力して、両者の最大公約数を求めて、最小公倍数の方法1:

import datetime
start=datetime.datetime.now()#  datetime             
#`           ，     `
temp1=input('input one number:')
temp2=input('input other number:')#  input（）         ，    。
a=int(temp1)
b=int(temp2)
c=a*b
while b:
        a,b=b,a%b
print('     :',a)
print('     :',c//a)
end=datetime.datetime.now()
print(end-start)

##input one number:24
input other number:9
     : 3
     : 72
0:00:03.363582

方法2:

import datetime
start=datetime.datetime.now()
def gcd(a,b):
    if (a%b==0):
        return b
    return gcd(b,a%b)
temp1=input('input one number:')
temp2=input('input other number:')#  input（）         ，    。
a=int(temp1)
b=int(temp2)
print('     :',gcd(a,b))
print('     :',a*b//gcd(a,b))
end=datetime.datetime.now()
print(end-start)
##
input one number:24
input other number:9
     : 3
     : 72
0:00:03.272271

方法3:この方法はまず最小公倍数を求めてから最大公約数を求める.2つの大きな数が入力されると、プログラムの実行が遅くなります.例えば(1000001)

import datetime
start=datetime.datetime.now()
temp1=input('input one number:')
temp2=input('input other number:')#  input（）         ，    。
a=int(temp1)
b=int(temp2)
c=max(a,b)
d=a*b
while c%a!=0 or c%b!=0:
    c+=1
print('     :',c)
print('     :',d//c)
end=datetime.datetime.now()
print(end-start)
##
input one number:24
input other number:9
     : 72
     : 3
0:00:06.003796

方法1と2のプログラムの実行時間はほぼ同じであることがわかるが,方法3は比較的時間がかかる.特に2つの大きな数の時.