※当サイトの記事には、広告・プロモーションが含まれます。

Java に限らないけど、 最小公倍数(LCM: Least Common Multiple)は、最大公約数(GCD: Greatest Common Divisor)が分かれば求まるらしい

f:id:ts0818:20190730202047j:plain

移動式の「デカルト座標」、「因数」と言えば、そうだね、映画『CUBE(監督:ヴィンチェンゾ・ナタリ)』だね!はい、どうもボクです。

というわけで、今回も Java の話です。

 

最小公倍数とは

今日も、Wikipediaさんに聞いてみた。

最小公倍数(さいしょうこうばいすう、least common multiple)とは、ではない複数の整数公倍数のうち最小の自然数をさす。

最小公倍数 - Wikipedia

とあり、

公倍数(こうばいすう)とは、2つ以上の整数に共通な倍数。例えば、の公倍数は-18,-12,-6,0,6,12,18などである。ただし、算数では、倍数にを含めないので、公倍数にもを含めない。

公倍数のうち、正で最小のものを最小公倍数という。上の例でいうと、の最小公倍数はである。

公倍数 - Wikipedia

であると。

んで、2つの整数の場合だと、

正整数に対して、最大公約数と最小公倍数との間には

という関係がある。

最小公倍数 - Wikipedia

が成りたつんだと。

つまり、最大公約数が求まれば、自ずと、最小公倍数が求まるのだと。

だが、しかし!

しかし、この関係式は3つ以上の正整数に対しては一般には成立しない。例えば、とすると、であるが、である。

最小公倍数 - Wikipedia

とあるように、3つ以上の整数になってくると成り立たないらしい...

3つ以上の整数になってくると、

多項式でない公倍数のうち、最も次数の低いものを最小公倍数という。例えば、の最小公倍数はである。

多項式の最小公倍数は定数倍を除いて1つしか存在しない。

最小公倍数 - Wikipedia

って感じになるらしいですと...。 

↓ 3つの整数だと、

x(x+1)(x-1) 、 x(x-1) + (x-1)((x+1)(x+1)-x)
x(x+1)(x+1) 、 (x-1)(x+(x+1)(x+1)-x)
x(x+1)(x+1) 、 (x-1)(x+1)(x+1)

↓ 最小公倍数は、
x(x+1)(x+1)(x-1)

ってことらしい...

っていうか、3次元以上の場合どうすれば良いんですかね...

ちなみに、4次元までしか、公式が存在しないらしい...

enjoymath.pomb.org

 

再帰処理で最小公倍数が求まるらしい

言語はPHPになるけれども、

qiita.com

⇧ 上記サイト様が、3つ以上の整数の場合の最小公倍数を求めてますね。

 

というわけで、Javaを使って求めてみますか。

ちなみに、最大公約数は、 

ts0818.hatenablog.com

⇧  この回の記事で求めていますが、今回は、最小公倍数を求めるために、最大公約数の求め方も修正してます。

というわけで、Eclipse を起動し、適当なJavaプロジェクトを作成し、クラスも作成。

f:id:ts0818:20190803174614p:plain

ソースコードはこんな感じで。

package main;

import java.math.BigInteger;
import java.util.Objects;
import java.util.stream.Stream;

public class LeastCommonMultiple {

  public static void main(String[] args) {
    // TODO 自動生成されたメソッド・スタブ
    // 最小公倍数を求めたい、数
    BigInteger[] bigIntArr = {
        BigInteger.valueOf(290021904),
        BigInteger.valueOf(927964716),
        BigInteger.valueOf(826824516),
        BigInteger.valueOf(817140688)
    };
    //    BigInteger[] bigIntArr = {
    //        BigInteger.valueOf(2),
    //        BigInteger.valueOf(12),
    //        BigInteger.valueOf(36),
    //        BigInteger.valueOf(18)
    //    };
    // 最大公約数
    System.out.println("最大公約数: " + gcd(bigIntArr));
    // 最小公倍数
    System.out.println("最小公倍数: " + lcm(bigIntArr));
  }

  // 最小公倍数(対象のすべての整数)
  public static BigInteger lcm(BigInteger... arr) {
    return Stream.of(arr).reduce((x, y) -> createLcm(x, y)).orElse(BigInteger.ONE);
  }

  //最小公倍数(指定した2つの整数)
  public static BigInteger createLcm(BigInteger x, BigInteger y) {
    return x.multiply(y)
        .divide(Objects.nonNull(creategcd(x, y)) ? creategcd(x, y) : BigInteger.ONE);
  }

  // 最大公約数(指定した2つの整数)
  public static BigInteger creategcd(BigInteger x, BigInteger y) {
    return (Objects.nonNull(x) ? x : BigInteger.ONE).gcd(y);
  }

  // 最大公約数(対象のすべての整数)
  public static BigInteger gcd(BigInteger[] arr) {
    return Stream.of(arr)
        .reduce(BigInteger::gcd)
        .orElse(BigInteger.ZERO);
  }
}

んで、実行してみる。

f:id:ts0818:20190803175027p:plain

f:id:ts0818:20190803174946p:plain

最小公倍数が上手くいってるのか分かりづらいので、配列の要素の整数を小さい値にしてみて実行。

f:id:ts0818:20190803175220p:plain

「2」「12」「36」「18」の最小公倍数は、「36」になっているので、なんとなく上手くいってるような気がするということで。

なんか、もっとエレガントなコーディングができるようになりたいもんですね...

 

ちなみに、勘違いしてたんだけど、reduce 自体は、再帰処理じゃないらしい...

qiita.com

gloryof.hatenablog.com

reduce(BinaryOperator<T> accumulator)

結合的な累積関数を使ってこのストリームの要素に対してリダクションを実行し、リデュースされた値が存在する場合はその値を記述するOptionalを返します。

Stream (Java Platform SE 8)

とあり、

リダクション操作(折りたたみとも呼ばれる)は、一連の入力要素を受け取り、結合操作を繰り返し適用することでそれらを結合し、単一のサマリー結果を出力します(一連の数値の合計または最大値の検索や、リストへの要素の蓄積など)。ストリーム・クラスには、reduce()collect()と呼ばれる複数の形式の汎用リダクション操作と、sum()max()count()など、複数の特殊化されたリダクション形式が含まれています。

もちろん、そのような操作は、次のように単純な順次処理ループとして簡単に実装できます。


    int sum = 0;
    for (int x : numbers) {
       sum += x;
    }

java.util.stream (Java Platform SE 8)

つまり、単なるループ処理だと(涙)。 

なので、再帰処理じゃなくても、最小公倍数を求めていけるってことですかね... 

 

う~ん、なんかモヤモヤ感が今日もまた残るけど...

今回はこのへんで。

2021年4月20日(水)追記:↓ ここから

「StreamAPI 」とか使わずに実装しておられる方もおりました~。

www.geeksforgeeks.org

2021年4月20日(水)追記:↑ ここまで