今回は最小公倍数・最大公約数をテーマに考えてみたいと思います.
2つの整数m,nの最小公倍数・最大公約数を求めるプログラムを書きたい.
n = int(input())
m = int(input())
min_factor = [False for i in range(max(m,n)+1)]
min_factor[0] = True
min_factor[1] = True
# 最小の素因数を求める
for i in range(2,int(max(m,n)**0.5)+1):
if min_factor[i] == False:
p = i
min_factor[i] = p
for j in range(p*p,max(m+1,n+1),p):
if min_factor[j] == False:
min_factor[j] = p
for i in range(max(m,n)+1):
if min_factor[i] == False:
min_factor[i] = i
# 最小の素因数を使って素因数分解を行う
num_ = n
div_list_n = []
while n > 1:
div_list_n.append(min_factor[n])
n = int(n/min_factor[n])
num_ = m
div_list_m = []
while m > 1:
div_list_m.append(min_factor[m])
m = int(m/min_factor[m])
素因数分解はO(log(n))の計算量のプログラムでした.
次に以下のコードを使って,最小公倍数・最大公約数を求めます.
# LCM: 最小公約数 GCD:最大公倍数
GCD = []
for i in range(len(div_list_m)):
factor = div_list_m[i]
if factor in div_list_n: # 共通していればGCDの要素に追加
GCD.append(factor)
div_list_n.remove(factor)
gcd = 1
for i in range(len(GCD)):
gcd *= GCD[i]
lcm = int(m_*n_/gcd) # m*nをgcdで割ればlcm
print(gcd,lcm)
素因数の数だけ繰り返し操作をしますが,素因数の個数は高々log(n)なので,計算量はO(log(n))ですね.
アルゴリズム全体の計算量としてはO(log(n))となります.
これを一つの関数にまとめたものが以下のコードです.
def gcd_lcm(m,n):
m_ = m
n_ = n
min_factor = [False for i in range(max(m,n)+1)]
min_factor[0] = True
min_factor[1] = True
# 最小の素因数を求める
for i in range(2,int(max(m,n)**0.5)+1):
if min_factor[i] == False:
p = i
min_factor[i] = p
for j in range(p*p,max(m+1,n+1),p):
if min_factor[j] == False:
min_factor[j] = p
for i in range(max(m,n)+1):
if min_factor[i] == False:
min_factor[i] = i
# 最小の素因数を使って素因数分解を行う
num_ = n
div_list_n = []
while n > 1:
div_list_n.append(min_factor[n])
n = int(n/min_factor[n])
num_ = m
div_list_m = []
while m > 1:
div_list_m.append(min_factor[m])
m = int(m/min_factor[m])
# LCM: 最小公約数 GCD:最大公倍数
GCD = []
for i in range(len(div_list_m)):
factor = div_list_m[i]
if factor in div_list_n:
GCD.append(factor)
div_list_n.remove(factor)
gcd = 1
for i in range(len(GCD)):
gcd *= GCD[i]
lcm = int(m_*n_/gcd)
print(gcd,lcm)
大きな数についてはエラトステネスの篩を応用したもののほうが速いかもしれませんが,
そうでない数についてはこちらのほうが速いかもしれません.
こちらはO(√n)の計算量です.
def prime_div(n):
div_list = []
n_ = n
div_num = 2
while div_num <= int(n_**0.5)+1:
if n%div_num == 0:
div_list.append(div_num)
n = n/div_num
else:
div_num += 1
if n < div_num:
break
if n != 1:
div_list.append(int(n))
return div_list
def gcd_lcm2(m,n):
m_ = m
n_ = n
div_list_m = prime_div(m)
div_list_n = prime_div(n)
# LCM: 最小公約数 GCD:最大公倍数
GCD = []
for i in range(len(div_list_m)):
factor = div_list_m[i]
if factor in div_list_n:
GCD.append(factor)
div_list_n.remove(factor)
gcd = 1
for i in range(len(GCD)):
gcd *= GCD[i]
lcm = int(m_*n_/gcd)
print(gcd,lcm)
ここまでは素因数分解を行って最小公倍数・最大公約数を求めました.
ですが,その難しさを根拠に暗号システムが作られるほどの素因数分解をするのは大変です.
素因数分解をせずに最小公倍数・最大公約数を求めることはできないのでしょうか?
そこで登場するのがユークリッドの互除法です.
まずは,そのアルゴリズムについて説明します.
def gcm(x,y):
if y == 0:
return x
elif x == 0:
return y
else:
if x >= y:
return gcm(x%y,y)
if x < y:
return gcm(x,y%x)
x = int(input())
y = int(input())
print(gcm(x,y),int(x*y/gcm(x,y)))
O(log(n))の計算量ですが,リストを使わず割り算だけで求めている分,前の2つより高速です.
計算量のオーダー自体は同じなのでnを"十分に"大きくすれば同じくらいの速さに収束するのかもしれません(?)
数学をやっていると「高々有限」や「極限を取れば」と簡単に言いたくなりますが,コンピュータの世界で理論上の正しさを過信してしまうと痛い目にあいます.
(学生時代に「極限取れば収束するんでしょ?」と情報系の教官に言ったら怒られました(苦笑))