素因数分解 (EPOCH@まつやま - 本選 2)

前回の AWK Users JP :: 友愛数 (EPOCH@まつやま - 本選 1) に続いて 2 問目で、素因数分解です。 本選第 1 ステージの問題 (PDF) の 2 問目になります。 既に素因数分解はAWK Users JP :: 素因数分解に代表的な素因数分解の解法を書いていますが、何もない状態ではなかなか思い出せないものです。

AWK Users JP :: EPOCH@まつやまの例題を解いてみるの中でも登場している約数を使って解いてみます。 つまり、2 以上の整数で自分以外で割りきれなければ素数とみなすことで素数判定をし、その素数で割っていきます。

#! /usr/local/bin/gawk -f
# epoch_problem_H2.awk
# 素因数分解
# usage: gawk -f epoch_problem_H2.awk file

{
    num = $0;

    # 1 は素数ではないため、ループは 2 からスタート
    for (i = 2; i <= num; i++) {
        # 素数かどうかの判定
        count = 0;
        for (j = 2; j <= i; j++) {
            if (i % j == 0) {
                count++;
            }
        }

        # 割りきれるものが 1 回、つまり自分自身だけの場合が素数
        if (count == 1) {
            # 割って 0 になる限り割る
            while (num % i == 0) {
                ans = ans i "*";
                num = num / i;
            }
        }
    }

    sub(/\*$/, "", ans);

    print ans;
}

もちろん再帰的な解法もあると思いますが、問題例には再帰を使わなければ解けないような問題はなかったので、再帰は使っていません。

答え合わせをしてみます。

$ echo '10' | gawk -f epoch_problem_H2.awk
2*5

$ echo '200' | gawk -f epoch_problem_H2.awk
2*2*2*5*5

$ echo '3000' | gawk -f epoch_problem_H2.awk
2*2*2*3*5*5*5

この問題は問題例を良く理解していれば解ける問題と言えるでしょう。