一連の数値の最大公約数と最小公倍数を計算する最も簡単な方法は何でしょうか? この情報を見つけるために使用できる数学関数は何ですか?
ベストアンサー1
私は使ったことがあるユークリッドのアルゴリズム2 つの数値の最大公約数を見つけます。これを繰り返して、より大きな数値セットの GCD を取得できます。
private static long gcd(long a, long b)
{
while (b > 0)
{
long temp = b;
b = a % b; // % is remainder
a = temp;
}
return a;
}
private static long gcd(long[] input)
{
long result = input[0];
for(int i = 1; i < input.length; i++) result = gcd(result, input[i]);
return result;
}
最小公倍数は少し難しいですが、おそらく最も良い方法はGCDによる削減これも同様に反復できます。
private static long lcm(long a, long b)
{
return a * (b / gcd(a, b));
}
private static long lcm(long[] input)
{
long result = input[0];
for(int i = 1; i < input.length; i++) result = lcm(result, input[i]);
return result;
}