見出し画像

ちょっとアルゴニズム - GCD,LCM

donguri

GCDとはGreatest Common Divisor、最大公約数です。最古のアルゴリズムということです。すごいです。

そこで、今回はLeast Common MultipleはLCM、最小公倍数の算出をしてみます。まず、GCD(最大公約数)ですが。Swiftで書きます。

func gcd(_ m: Int, _ n: Int) -> Int {
   let r: Int = m % n
   if r != 0 {
       return gcd(n, r)
   } else {
       return n
   }
}

実行してみます。

gcd(12,8)

とすると"6"と答えがでます。

wikiでの説明は以下。

b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
x = 12、y = 18 とすると、x を y で割った余り r は 12
y = 18 を r = 12 で割った余り r_1 は 6
r = 12 を r_1 = 6 で割った余りは r_2 は 0
よって、このときの割る数「6」が 12 と 18 の最大公約数である

これを元に

コードを変更します。

func gcd(_ m:Int,_ n:Int)->Int{
 
   if n == 0{
       return m
   }else{
       return gcd(n , m % n)
   }
}

こちらの方が定義からいうと理解しやすいです。

LCM、最小公倍数は上記の"gcd()"を使って

func lcm(_ m: Int, _ n: Int)->Int{
   return  m * n / gcd(m, n)
}

として実行してやります。

lcm(10,8)

"40"と答えが出ます。

これをPythonでやると

def gcd(x, y):
   if y == 0:
       return x
   else:
       return gcd(y, x % y)
if y == 0:

この条件以外で実行されます。

print(gcd(8,10))

答えが"2"と出ます。次最小公倍数です。

def lcm(a, b):
	return a * b // gcd (a, b)
print(lcm(10,8))

答えは"40"とでます。


この記事が気に入ったらサポートをしてみませんか？