プログラミング雑感  新JavaScript入門  JavaScript,Neo-Generation  掲示板  表紙
9. 因数分解(1)  11. 因数分解(3) 
プログラミング雑感
Written 5/25/02
10. 因数分解(2)
今回は2次の多項式を因数分解することを考えます。
■アルゴリズム
2次の多項式が因数分解できるとしたら、1次同士の積にしかなりえません。 
  a0 + a1x + a2x2 = (b0 + b1x)(c0 + c1x)
右辺を展開して、xの各次の係数を比較すると、 
  a0 = b0c0
  a1 = b0c1 + b1c0
  a2 = b1c1
与えられた整数 a0, a1, a2 に対し、 上の3式を満たす整数 b0, b1, c0, c1 を求めればよいわけです。 3式のうちの上の式から、b0 と c0 は a0 の約数になります。 同様に下の式から、b1 と c1 は a2 の約数になります。 したがって、求める4つの変数の組合せは有限となり、 このうちで真ん中の式を満たすものがあれば、それが解となります。
例えば、次のような多項式を考えましょう。 
  2 - 5x + 2x2
b0 > 0 としてもよいので、 
  (b0, c0) = (1, 2), (2, 1)
  (b1, c1) = (1, 2), (2, 1), (-1, -2), (-2, -1)
すなわち8通りの組合せがあり、この中で、 
  -5 = b0c1 + b1c0
を満たすのは、 
  (b0, b1, c0, c1) = (1, 2, -2, -1)
ですから、結局、 
  2 - 5x + 2x2 = (1 - 2x)(2 - x)
となります。
と説明していくと中学生でもできるものですが、 実際にプログラムを組もうと思うとけっこうたいへんです。
■エラトステネスのふるい
まず、素因数分解をしなければならないのですが、 そのために素数の集合を得ます。
素数を求めるには「エラトステネスのふるい」というアルゴリズムを使います。 これは、例えば100までの素数を求めたいとき、1から100まで数字を並べておいて、 2から10(=sqrt(100))までの整数の倍数に線を引いていき、 残った1以外の整数が素数となります。
実際には、素数の倍数のみを使えばいいのは明らかです。 また、ふるいをかけるのはその素数の自乗から始めれば十分であることも明らかです。 素数であることは、例えば3まで「ふるい」が行われたら、 9(=3*3)まででのふるいで残った数字が素数となります。 これを順々に行っていきます。 
   1   2   3   4   5   6   7   8   9  10
  11  12  13  14  15  16  17  18  19  20
  21  22  23  24  25  26  27  28  29  30
  31  32  33  34  35  36  37  38  39  40
  41  42  43  44  45  46  47  48  49  50
  51  52  53  54  55  56  57  58  59  60
  61  62  63  64  65  66  67  68  69  70
  71  72  73  74  75  76  77  78  79  80
  81  82  83  84  85  86  87  88  89  90
  91  92  93  94  95  96  97  98  99 100
      
ボタンを押していくと、右に素数が現れて、 その素数の倍数（自分自身を除いて）が消されていき、 最後に残った赤い数字が素数になります（IE4 or later only）。
■素因数分解
このようにして得られた素数で割っていき、素因数分解します。 素数が必要なのは次の値以下です。 
  plimit = sqrt(a)
  n = ps * pt * ... * pu * a
  (n : 素因数分解する整数, a : n を pi 以下の素数で割りつくした商
   pi : 今の素数)
同時にエラトステネスのふるいを行って素数を求めていきます。 
  pi * pi + 1 〜 pi+1 * pi+1 - 1 について p0, p1, ... , pi で割り、
  このうちどれでも割り切れなかった数が素数に追加される
  (p0 = 2, p1 = 3, ...)
考えやすいように素数の集合のオブジェクトを考えましょう。
これは整数を素因数分解するメソッド factorize を働かせると、 必要に応じて保持する素数が増えていくものです。 
  function p_numbers() {
    this.ary = [ 2 ];   //素数を並べた配列
    this.factorize = prime_factorize;
  }
素因数分解された結果は次のように格納することにします。 
  plqm...rn => [ p, l, q, m, ... , r, n ]
こうすると、あとから約数を得るときに便利です。
   
テキストボックスに自然数を入れてボタンを押すと、 上の配列の表現で素因数分解されます。 1のときは長さ0の配列です。
ソースは次にあります。 
  p_numbers.js (ファイルに保存にしてください)
使い方はソースを参照してください。
■約数
この素因数分解を使って約数を次々に得ます。
例えば、12の約数を得るとき、 
  12 = 22 * 3
だから、2つ素因数があって、それぞれが、 
  (20, 21, 22)
  (30, 31)
という値を取り得るので、(2+1)*(1+1)=6通りの値を取ります。
この6通りを0〜5までの整数に割り当てます。 
  0 => 0 + 0 * 3 => 20 * 30
  1 => 1 + 0 * 3 => 21 * 30
  2 => 2 + 0 * 3 => 22 * 30
  3 => 0 + 1 * 3 => 20 * 31
  4 => 1 + 1 * 3 => 21 * 31
  5 => 2 + 1 * 3 => 22 * 31
このようにして約数を次々得るためのオブジェクトを作ります。 
  function divisors(n, ps) {        //ps : p_numbersオブジェクト
    if(n < 1 || n % 1 != 0)         //自然数以外はお断り
        return;
    this.n = n;
    this.index = 0;                 //今の約数のID
    this.ary = ps.factorize(n);     //素因数分解
    this.length = this.ary.length;
    this.size = 1;                  //約数の総数
    for(var i = this.length - 1; i >= 0; i -= 2)
        this.size *= (this.ary[i] + 1);
    this.getdivisor = getdivisor;   //約数を得る
    this.atEnd = false;             //最後までいったか
    this.MoveNext = div_MoveNext;   //次の約数へ
  }
   
テキストボックスに自然数を入れてボタンを押すと、 約数が次々に表示されます。
ソースは次にあります。 
  p_numbers.js (ファイルに保存にしてください)
これでやっと因数分解ができます。
■2次多項式の因数分解
もう一度求める係数の関係を書いておくと、 
  a0 = b0c0
  a1 = b0c1 + b1c0
  a2 = b1c1
これを実現すればよいです。
   
テキストボックスに2次の多項式を入れてボタンを押すと、 因数分解の結果が表示されます。 例えば、"x^2-x-2"と入力すると"(x+1)(x-2)"と表示されます。
ソースは次にあります。 
  polynomial2.js (ファイルに保存にしてください)
次からはより高次の多項式の多項式を考えていきます。
first, prev, next, exit