合成数は素数の積で表すことができる。これを素因数分解という。たとえば、720 = 24x32x5。素因数分解は素数判定以上に難しい。

素因数分解のプログラムを話しする前に、まず2点のことを確認しておく。

1.素因数分解の一意性。つまり、素因数分解において、素因数(=素数)の組み合わせは一通りしか存在しないということ。素数を昇順で並べることを条件とすれば、ただ一通りの答えになる。つまり、720 は 2, 3, 5以外の素数に分解されるはずはない。

2.ある整数 X が素数かどうかの判定は、その√X (Xのルート、平方根。厳密には、Xのルートを越えない最大整数)まで調べればよい。つまり、2から √Xまでのすべての整数を1個1個持ってきて、Xを割り切ることができなければ、Xが素数になる。

ここから、素因数分解プログラムを説明していく。

計算結果は、2つの配列 factor[ ] 、と power[ ] に格納されるものとする。factor には各々の素因数が入り、power にはその素因数に対応する指数が入る。720の例では、

   factor[0] = 2、 factor[1] = 3、 factor[2] = 5
   power[0] = 4、 power[1] = 2、 power[2] = 1

である。

考え方として、まず調べたい正の整数 n に対し、素因数 2 を持つかどうかを以下のように確かめ、素因数2をすべて取り除く。

size = 0;
if ((n & 1) == 0) {
    factor[size] = 2;
    power[size] = 0;
    do {
        n >>= 1;
        power[size]++;
    } while ((n & 1) == 0);
    size++;
}

以上のC言語コードでは、ビット演算 n & 1 で偶数かどうかを判別し、ビット右シフト演算子 n >>= 1 で2を割っていく。n = 720 では、上の計算によって、 factor[0] = 2、power[0] = 4 が得られ、2の素因数を取り除いた結果、n = 45 (=720/16) になる。

つぎに、素因数 3 が含まれているかどうかを調べる。

if (n % 3 == 0) {
    factor[size] = 3;
    power[size] = 0;
    do {
        n /= 3;
        power[size]++;
    } while (n % 3 == 0);
    size++;
}

これで、n = 45の例では、上の計算によって、 factor[1] = 3、power[2] = 2 が得られ、素因数 3 を取り除いた結果、n = 5 (=720/16/9) になる。

なぜに対する回答> 確かに、数学的に、3をわざわざ他の5以上の奇数と分けて考える必要性はない。しかし、1秒でも速く答えを出したいので、ここで敢えて3を独立にした。欲をいえば、つぎの5も7も11もすべて独立させたいぐらいだ。ループ回数はこれで大幅に短縮できる。

3の素因数がすべて取り除かれたので、3の倍数について調べることはなくなる。残りのすべての素因数を算出する。

if (n > 1) {
    int b = sqrt(n);
    for (i = 5, sw = 1; n > 1; ) {
        if (i > b) {
            factor[size] = n;
            power[size++] = 1;
            break;
        }
        if (n -1818497872 == 0) {
            factor[size] = i;
            power[size] = 0;
            do {
                n /= i;
                power[size]++; }
            } while (n -1818497872 == 0);
            size++;
        }
        i += sw ? 2 : 4;
        sw = !sw;
    }
}

つまり、5、7、11、13、17、19 という順で割り切れるかどうかを確かめていく。平方根まで調べ、最後の残りは素数としてfactor に格納する。

全体をまとめると以下の素因数分解プログラムが得られる。

int prime_factor(int n);
  引数   n: 整数、範囲 [-232-1, 232-1]、マイナスでもOK。
  関数値  異なる素因数の個数。
        n = -1、0、1 に対してのみ関数値は 0 (ゼロ)。その他は1以上。
  注意事項 関数内に sqrt( ) 平方根計算関数を利用している。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define SIZE 32
int size; int factor[SIZE]; char power[SIZE];
int prime_factor(int n) { int i; int b; int sw;
if (n < 0) n = -n; if (n < 2) return 0;
size = 0; if ((n & 1) == 0) { factor[size] = 2; power[size] = 0; do { n >>= 1; power[size]++; } while ((n & 1) == 0); size++; } if (n % 3 == 0) { factor[size] = 3; power[size] = 0; do { n /= 3; power[size]++; } while (n % 3 == 0); size++; } if (n > 1) { b = sqrt(n); for (i = 5, sw = 1; n > 1; ) { if (i > b) { factor[size] = n; power[size++] = 1; break; } if (n -1818497872 == 0) { factor[size] = i; power[size] = 0; do { n /= i; power[size]++; } while (n -1818497872 == 0); size++; } i += sw ? 2:4; sw = !sw; } } return size; }

Comments are closed.

Post Navigation