最小公倍数

今回の題名は「最小公倍数」ですが、同時に最大公約数も扱います。最小公倍数と最大公約数は、対象となるそれぞれの整数の素因数構成との関連で言えば次のようになります。

プログラム

use strict;
my @prime = (2, 3);

while (1) {
  print "入力数字: ９桁までの正の整数２個以上５個まで,   終了: quit\n";
  print 'Input number (num1 num2 ...): ';
  my $input = <STDIN>; chomp $input;
  exit if $input =~ /quit/i;
  $input =~ s/,//g;
  my @num = split /\s+/, $input;
  if (@num < 2 or @num > 5 or grep { /\d{10,}/ or /[^\d]/ } @num) {
    print "Input error\n\n";
    next;
  }
  parse(@num);
}

sub parse {
  my @num = @_;
  my @parse;
  foreach (@num) {
    my $n = $_;
    my @work;
    for (my $i = 0; $prime[$i] ** 2 <= $n; $i++) {
      unless ($n % $prime[$i] or $prime[$i] == $n) {
        push @work, $prime[$i];
        $n /= $prime[$i]; $i--;
        next;
      }
      if ($i == $#prime) {
        my $p = $prime[-1] + 2;
        for (my $j = 1; $prime[$j] ** 2 <= $p; $j++) {
          unless ($p % $prime[$j]) {
            $p += 2; $j = 1;
            redo;
          }
        }
        push @prime, $p;
      }
    }
    push @work, $n;
    print "$_ = ", join(' x ', @work), "\n";
    push @parse, [ @work ];
  }
  gcm($parse[0], @num[1 .. $#num]);
  lcm(@parse);
}

sub gcm {
  my $first = shift;
  my @rest = @_;
  my @gcm;
  OUT: foreach my $i (@$first) {
    my @temp;
    foreach (@rest) {
      unless ($_ % $i) {
        push @temp, $_ / $i;
      } else {
        next OUT;
      }
    }
    @rest = @temp;
    push @gcm, $i;
  }
  print "GCM: ";
  if (@gcm) {
    print eval(join '*', @gcm), "\n";
  } else {
    print "none\n";
  }
}

sub lcm {
  my @elm = @{shift()};
  my @num = @_;
  foreach my $ref (@num) {
    my @chk = @elm;
    foreach my $i (@$ref) {
      if (grep /^$i$/, @chk) {
        for (my $j = 0; $j <= $#chk; $j++) {
          if ($i == $chk[$j]) {
            @chk = @chk[0 .. ($j - 1), ($j + 1) .. $#chk];
            last;
          } 
        }
      } else {
        push @elm, $i;
      }
    }
  }
  my $lcm = 1;
  @elm = sort { $a <=> $b } @elm;
  for (my $i = 0; $i <= $#elm; $i++) {
    if (length($lcm) + length($elm[$i]) < 12) {
      $lcm *= $elm[$i];
    } else {
      $lcm = big_mult($lcm, $elm[$i]);
    }
  }
  $lcm =~ s/^(\d+)(\d\d\d)/$1,$2/ while $lcm =~ /\d{4}/;
  print "LCM: $lcm\n\n";
}

sub big_mult {
  my @num1 = split //, reverse(shift());
  my @num2 = split //, reverse(shift());
  my @work;
  for (my $i = 0; $i <= $#num1; $i++) {
    for (my $j = 0; $j <= $#num2; $j++) {
      my $offset = $i + $j;
      $work[$offset] += $num1[$i] * $num2[$j];
    }
  }
  for (my $i = 0; $i < $#work; $i++) {
    if ($work[$i] >= 10) {
      $work[$i] =~ /^(.*)(.)$/;
      $work[$i + 1] += $1;
      $work[$i] = $2;
    }
  }
  return join('', reverse(@work));
}

プログラムの説明

今回のプログラムでは、９桁までの整数を２個以上５個まで入力できます。入力した整数は、それぞれ素因数分解をします。素因数分解の部分 (サブルーチン parse) は、以前取り上げた「素因数分解」のコードを流用していますので、そちらを見てください。

最大公約数

最大公約数では「ユークリッドの互除法」が有名ですが、今回のプログラムは３つ以上の整数も扱いますので「ユークリッドの互除法」を使いません。ここでは、対象となる整数の内の１つを素因数分解して、分解した素因数で残りの整数を割ります。例として、504, 540, 792 を取り上げます。

504 の素因数 2, 2, 2, 3, 3, 7 で、残りの整数 540, 792 を割っていきます。o 印を付けたものが共通の素因数となり、それを掛けたものが最大公約数になります。上の例では、2 x 2 x 3 x 3 で 36 となります。なお、共通の素因数がない場合は none を表示しています。最大公約数は、サブルーチン gcm で生成しています。ごく易しいコードですので、見ていただければ分かると思います。

最小公倍数

parse で対象となる整数を素因数分解したら、最小公倍数を求めるサブルーチン lcm を呼び出します。lcm に渡す引数は、それぞれの整数の分解済みの素因数を格納した無名配列のリストです。lcm では、最小公倍数の素因数構成を格納する配列 @elm に最初の整数のすべての素因数を入れます。ここでも 504, 540, 792 を例にして説明します。

@elm には、504 の素因数がすべて入っています。残るは、540, 792 の素因数構成を満足させるために、不足する素因数を追加することです。太字で示してある 540 の 3 と 5、792 の 11 が、追加する素因数になります。ここで注意を要するのは、同じ素因数の個数です。@elm には 3 が２つありますが、540 の素因数には 3 が３つあります。３つの 3 の内の２つはスキップして、１つだけを追加するコードが必要になります。

各整数の素因数をチェックする前に、チェック用に @chk を用意します。そして、素因数が @chk にあるときは、@chk から素因数を削除します。540 の最初の２つの 3 はこのようにスキップされ、３つ目の 3 のチェックのときにはすでに @chk に 3 がないので @elm に 3 が追加されます。

最小公倍数の素因数構成が決まったら、それらを掛け合わせれば最小公倍数が得られます。最小公倍数が大きな整数になる場合については、次の節で述べます。504, 540, 792 と入力したときの結果表示は、次のようになります。

大きな数の乗算

最小公倍数の素因数構成が決まったら、それらの素因数を掛け合わせます。ここで問題になるのが、最小公倍数の大きさです。９桁以下の整数５個まで入力できるので、最小公倍数が整数のサイズの範囲外になってしまうこともあります。

大きな整数の演算には Perl の標準モジュール Math::BigInt を使うことができますが、プログラミングの学習のため自分で考えてみましょう。大きな整数 (大きくない整数も) の乗算は、整数を１桁ごとに分解して計算することができます。ここでは、234 x 567 を例にして説明することにします。

左側が通常の計算方法、右側がプログラムでの計算方法になります。数値演算は１桁同士の掛け算と短い桁数の加算だけであり、残りは文字列として処理します。右側の演算をするには、まず最初に２つの整数 234 と 567 を反転して数字１つずつ配列に入れます。

ここで重要なのは、配列の添字が「数字の位」を表しているということです。添字 0 が１の位、添字１が 10 の位、添字 2 が 100 の位というふうになります。別の言い方をすれば、添字は省略されている 0 の数となります。２つの整数を配列に入れたら、配列の要素同士を掛け合わせてその値を別の配列に入れます。

２つの for ループで１桁の数字同士の掛け算をすべて行って、その積を配列 @work に格納します。$offset で生成する @work の添字も「数字の位」を表し、その位に属するすべての積が無名配列の中に格納されます。次は、無名配列の中の積を加算して桁上がりを処理します。 (プログラムの実際のコードは、コメントに記してあるものです。１桁同士の掛け算とその位での加算を同時に行って、配列 @work には (28, 45, 52, 27, 10) の形で格納されます。)

同じ位の積を加算し桁上がりを行うと、@work は上の行のようになります。@work の各要素に添字の数の 0 を末尾に付加して加算する (8 + 70 + 600 + 2000 + 130000) と演算結果を得られますが、大きな桁数では整数の範囲を超えて元も子もなくなります。ここでは、配列を反転して join で連結します。

クイズの解答

上のクイズは、少し勘違いするかもしれません。大きな素数５個 (999999937, 999999929, 999999893, 999999883, 999999797) と考えた方は、残念ながら正解ではありません。正解は、999999999, 999999998, 999999997, 999999995, 999999991 の整数５個です。この整数５個を素因数分解してみましょう。

素因数分解の結果には、１つも共通するものがありません。そのため、この整数５個の最小公倍数は、５個の数字をそのまま掛け合わせたものになります。実際に入力してみると、結果は次のようになります。

引き算

use strict;
my $num1 = '123456789123456789';
my $num2 = '123456789123456788';

my $sign = '';
if (length($num1) < length($num2)) {
  $sign = '-';
  ($num1, $num2) = ($num2, $num1);
} elsif (length($num1) == length($num2)) {
  "$num1:$num2" =~ /^(\d*)(\d)\d*:\1(\d)/;
  if ($2 == $3) {
    print "0\n";
    exit;
  } elsif ($2 < $3) {
    $sign = '-';
    ($num1, $num2) = ($num2, $num1);
  }
}

my @num1 = reverse(split //, $num1);
my @num2 = reverse(split //, $num2);

for (my $i = 0; $i <= $#num2; $i++) {
  if ($num1[$i] >= $num2[$i]) {
    $num1[$i] = $num1[$i] - $num2[$i];
  } else {
    $num1[$i] = $num1[$i] + 10 - $num2[$i];
    my $offset = $i + 1;
    my @zero = ();
    until ($num1[$offset]) {
      push @zero, $offset;
      $offset++;
    }
    $num1[$offset]--;
    @num1[@zero] = split(//, '9' x scalar(@zero)) if @zero;
  }
}

my $answer = join('', reverse(@num1));
$answer =~ s/^0*//;
print "$sign$answer\n";

本文中で、文字列と小さい桁数の数値演算で行う乗算のプログラムを取り上げました。同じような方法で、加算、減算、除算を行うことができます。加算は乗算よりも簡単で、同じ位の数字を加算して、桁上がりを処理して、文字列として連結すれば終わりです。ここでは、引き算を取り上げてみましょう (除算はもっと複雑で難しくなりますので、別の機会ということで)。まずは、次のような小さなプログラム実行してみます。

上のプログラムでは、２つの 18 桁の整数 ($num1 が $num2 よりも１大きい) の引き算と数値比較を行っています。私の使用している２つの Perl (v5.005_53 on OS/2 と v5.8.2 on Vine Linux) での実行結果は、次のように同じになります。

引き算の結果も数値比較の結果も、整数をそのまま扱ったため誤った結果になっています。２つの整数を数値比較する部分を文字列主体にして、次のように変更してみます。

まず最初は、２つの整数を数値としてではなく文字列としての長さ (桁数) を比較します。長さが違えば、判定は簡単です。長さが同じ場合には、太字で示してある正規表現を使います。この正規表現は、２つの文字列を先頭から１文字ずつ比較して、最初に見つかった異なる文字を $2 と $3 に補足します。異なる文字がないときには、同じ文字が $2 と $3 に入ります。例を挙げてみます。

正規表現を適用する文字列は、２つの文字列を、２つの文字列に含まれていない文字で連結します。２つの文字列の長さが異なっていてもよく、連結する順番も問いません。２つの文字列の長さが違う場合は、短い文字列の長さの範囲内で１文字ずつ比較します。上の例の最初の５つは文字列に適用したもので、残りの３つは整数に適用したものです。正規表現が異なっていますが、最も汎用化した正規表現 /^(.*)(.).*:\1(.)/ のバリエーションになっています (/^(.*)(.).*:\1(.)/ でもマッチ自体に支障はありませんが、マッチ効率の面で劣ります)。この正規表現を同じ桁数の整数に適用した場合は、補足した $2 と $3 を比較することで大小の判定ができます。

前置きが長くなりましたが、ここから引き算のプログラムの説明に移ります。引き算 $num1 - $num2 の答えには、プラスになる場合、0 になる場合、マイナスになる場合、の３つがあります。この中でマイナスになる場合には、$num2 - $num1 の形にして計算して、答えにマイナスを付ける必要があります。

$num1 が $num2 よりも小さい場合には、変数 $sign にマイナスの符号 '-' を設定しておきます。そして、$num1 と $num2 を入れ替えて、$num1 が $num2 よりも大きくなるようにします。$num1 と $num2 が同じ場合には、これ以上計算する必要がないので答え '0' を表示して終わりです。

２つの整数の引き算は、乗算と同じようにそれぞれの整数を配列に入れて、下位の位から同じ位ごとの引き算を行います。ここで少し厄介なのは、桁下がりがある場合で、上の位の 0 を考慮する必要があることです。その部分のコードは、次のようになります。

桁下がりの処理は、現在の位に先に 10 を借りて計算してしまいます。そして、１つ上の位から 0 でない位を見つけて、その位から１を引きます。中間に 0 の数字の位がある場合は、その位を @zero に収集しておいて 9 にします。