GCD

[C#] 最小公倍数(LCM)を求めるアルゴリズムと実装

最小公倍数 – Least Common Multiple 最小公倍数 – Wikipedia 最小公倍数とは、0ではない複数の整数の公倍数のうち最小の自然数をさします。 最小公倍数の求めかた 2つの正整数(a, b)の最小公倍数は、最大公約数が求めれば簡単に求まります。なぜなら最大公約数と最小公倍数には以下のような性質があるためです。 a * b = Gcd(a, b) […]

[C#] ユークリッドの互除法で最大公約数を求める方法

最大公約数を求めるプログラム 2つの自然数の最大公約数を求めるアルゴリズムの1つに、ユーグリッドの互除法 があります。これをプログラムで実装する方法をまとめます。 ユークリッドの互除法とは ユークリッドの互除法 – Wikipedia 2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に […]