R言語 モモノキ＆ナノネと学習 もものきとRを始めよう

Rでデータ解析を始めよう016 複数の数(3つ以上)で最大公約数と最小公倍数を求める方法

モモノキ＆ナノネと一緒に統計ソフトRの使い方を学習していきます。

モモノキ＆ナノネと一緒にRで計算練習をやってみよう

ユークリッドの互除法を使って、複数の数で最大公約数と最小公倍数を求めてみる

ナノネ、統計解析用フリーソフト『R』を使って計算コードを書く練習をするよ。今回は複数の数の最大公約数と最小公倍数を求めてみよう。

モモノキ、最大公約数と最小公倍数を求めるだけ？？

うん、ただ求めるだけ。Rコード作成練習だよ。でもせっかくだから、2つの数同士だけじゃくて複数の数の最大公約数と最小公倍数を求めてみよう。

ラジャー。最大公約数と最小公倍数はどうやって求めるんだっけ？なんとか互除法とかあったような．．．。

最大公約数は『ユークリッドの互除法』で効率的に求めることができるよ。それから最小公倍数も最大公約数を使うことで簡単に計算できるよ。

『ユークリッドの互除法』、やりかた忘れたかも。

繰り返しの処理が必要だけど、二つの自然数で割り算して余りがゼロになったときの除数（分母）が最大公約数になるよ。余りがゼロでないときは、そのときの余りを次の計算の除数（分母）に、そのときの除数（分母）に使っていた数を次の計算の被除数（分子）に数を置き換える。その操作を余りがゼロになるまで延々と繰り返すと最大公約数が求まるよ。

言葉で表現すると少しややこしいけど、コード自体はすごく簡単だよ。

In [1]:

# 最大公約数（greatest common divisor）
# ユークリッドの互除法
gcd <- function(a, b){
    while(a %% b != 0){
        tmp <- b
        b <- a %% b
        a <- tmp
    }
    return(b)
}

少し思い出したかも。再帰とか使ってもコード書けたよね。

いろいろな書き方ができるから、互除法はお好みで実装してみてね。

最終的には複数の自然数で最大公約数と最小公倍数を求めるんだけど、最初はシンプルに二つの自然数でやってみよう。

ユークリッドの互除法の関数(gcd)は上で実装したから、二つの自然数の最大公約数はすぐに求められるよね。

In [2]:

# 最大公約数チェック
gcd(48, 32)
gcd(8, 12)
gcd(120, 160)

16

4

40

二つの自然数の最大公約数はOKそうだよ。

次は二つの自然数の最小公倍数だね。最小公倍数は『二つの自然数の積』を『二つの自然数の最大公約数』で割ると求められるよ。最小公倍数を求める関数（lcm）を実装してみよう。

In [3]:

# 最小公倍数（least common multiple）
# 2つの自然数の積 / 2つの自然数の最大公約数 -> 最小公倍数
lcm <- function(a, b){
    a * b / gcd(a, b) # 最大公約数を求める関数を再利用 
}

最小公倍数を求める関数を実装したよ。うまく動くかな？

In [4]:

# 最小公倍数チェック
lcm(4, 8)
lcm(16, 5)
lcm(24, 18)

8

80

72

関数の計算結果もOKそう。

二つの自然数でうまくいったから、次は本題の3個以上の自然数で求めてみよう。

3個以上の場合はどうやって求めるの？

キホン的には二つの自然数のときと考え方は一緒だよ。

もし、A,B,Cの3個の自然数があった場合で考えると、『AとBの最大公約数』と『C』との最大公約数がA,B,Cの最大公約数になるよ。つまり2つの自然数の最大公約数を求める操作を順次行えば、複数の自然数の最大公約数を求めることができるんだ。最小公倍数も同じ原理で求められるよ。

なるほど、対象を二つだけにしてそれを繰り返せばいいんだ。二つ用の関数はもう作ったから、再利用するだけで3個以上も対応できそう。

まずは、複数の自然数で最大公約数を求めてみる。

In [5]:

# 任意の自然数の最大公約数
data <- c(48, 32, 64, 96) # 2個以上の任意の自然数
N <- length(data)
n <- data[1]
for(i in 2:N){
    n <- gcd(n, data[i]) 
}
print(n) # dataの最大公約数

[1] 16

OK。続いて、複数の自然数で最小公倍数を求めてみる。

In [6]:

# 任意の自然数の最小公倍数
data <- c(12, 48, 17, 18) # 2個以上の任意の自然数
N <- length(data)
n <- data[1]
for(i in 2:N){
    n <- n * data[i] / gcd(n, data[i]) 
}
print(n) # dataの最大公約数

[1] 2448

In [7]:

# 簡易検算
print(2448 / data)
print(2448 %% data)

[1] 204  51 144 136
[1] 0 0 0 0

チェックした限りは、うまく動いているみたい。

たとえば、自然数Nまで最小公倍数とかも簡単に求められるよ。

In [8]:

# 任意の自然数の最小公倍数
data <- 1:10 # 1～10まで
N <- length(data)
n <- data[1]
for(i in 2:N){
    n <- n * data[i] / gcd(n, data[i]) 
}
print(n) # 自然数1～10までの最小公倍数

[1] 2520

In [9]:

# 簡易検算
print(2520 / 1:10)
print(2520 %% 1:10)

 [1] 2520 1260  840  630  504  420  360  315  280  252
 [1] 0 0 0 0 0 0 0 0 0 0

In [10]:

# 任意の自然数の最小公倍数
data <- 1:20 # 1～20まで
N <- length(data)
n <- data[1]
for(i in 2:N){
    n <- n * data[i] / gcd(n, data[i]) 
}
print(n) # 自然数1～20までの最小公倍数

[1] 232792560

In [11]:

# 簡易検算
print(232792560 / 1:20)
print(232792560 %% 1:20)

 [1] 232792560 116396280  77597520  58198140  46558512  38798760  33256080
 [8]  29099070  25865840  23279256  21162960  19399380  17907120  16628040
[15]  15519504  14549535  13693680  12932920  12252240  11639628
 [1] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

結果が大きな値になるけど、計算は一瞬だね。

複数の自然数で最大公約数と最小公倍数を求めるRの計算練習は以上で。
またね！

スポンサーリンク