２つの数字の最大公約数と最小公倍数‥‥これをプログラム的にどうするのか考えて見た。
まず最大公約数を求めて、二つの数を最大公約数で割った商をかけ合わせれば最小公倍数になる。
そのためには、共通して割れる素数を見つけ、どんどん割っていけばよい。割れなければ次の素数へ、これを繰り返す作業だ。
二つの整数を a,bとする。
最大公約数になる数字をcとする。
二つの数字を共通して割れる数字(約数)をiとする。
表の右端は例として、a=48 b=36 の場合を表示している。[]内の数字はループの回数。
| コード | 説明 | 具体例 | |
| c=1 | 最大公約数の初期値は1 | ||
| i=2 | 約数の初期値は2 | ||
| Do | Loop まで繰り返す | ||
| If (((a mod i)=0) and ((b mod i)=0)) then | もし aもbもiで割り切れるなら 以下の処理をする |
[1]OK [2]OK [3]NG [4]OK |
|
| a=a/i | aをiで割る | [1] a=24 [2] a=12 [4] a=4 |
|
| b=b/i | bをiで割る | [1] b=18 [2] b=9 [4] b=3 |
|
| c=c*i | 最大公約数になるcをi倍する | [1] c=2 [2] c=4 [4] c=12 |
|
| else | a,bどちらかが i で割り切れないなら 以下の処理をする |
||
| If i=2 then | |||
| i=3 | 割る数を3,5,7,…と増やす | [3] i=3 | |
| Else | |||
| i=i+2 | ※ | [5] i=5 | |
| End if | |||
| End if | |||
| Loop until ((a<i) or (b<i)) | aかｂが 割る数 i より 小さくなったら終わり |
[5] i=5 a=4,b=3 ループ終わり |
|
| print c | 最大公約数はc | c=12 | |
| print a*b*c | 最小公倍数はa*b*c | a=4､b=3 |
※ 本来ならｉは素数なのだが、簡略化するために3以降は奇数にしている。
a=48 b=36 の場合、最大公約数は12、最小公倍数は144となる。
