醜い数（アグリー・ナンバー）とは？n番目の醜い数を効率的に求めるC++プログラム

醜い数（アグリー・ナンバー）とは、素因数が2、3、5のみで構成される数のことです。1から15の範囲には、1、2、3、4、5、6、8、9、10、12、15の11個の醜い数が存在します。

一方、7、11、13はそれ自体が素数であるため醜い数には含まれません。また、14は素因数分解すると7が現れるため、これも醜い数ではありません。

この記事では、n番目の醜い数を求めるプログラムを、アルゴリズムの考え方から実際のC++コードまで詳しく解説します。

入力と出力

Input:
項番号を入力する。例：10
Output:
10番目の醜い数は12

アルゴリズム

getUglyNumbers(n)

入力： 項の個数。

出力： n番目の醜い数を求める。

Begin
    サイズnの配列uglyNumを定義する
    i2 := 0, i3 := 0, i5 := 0
    next2mul := 2, next3mul := 3, next5mul := 5
    next := 1
    uglyNum[0] := 1

    for i := 1 to n-1, do
        next := next2mul、next3mul、next5mulの中の最小値
        uglyNum[i] := next
        if next = next2mul, then
            i2 := i2 + 1
            next2mul := uglyNum[i2] * 2
        if next = next3mul, then
            i3 := i3 + 1
            next3mul := uglyNum[i3] * 3
        if next = next5mul, then
            i5 := i5 + 1
            next5mul := uglyNum[i5] * 5
    done
    return next
End

アルゴリズムのポイント

このアルゴリズムの鍵となるのは動的計画法（DP）の考え方です。既に求めた醜い数にそれぞれ2、3、5を掛け合わせた値も必ず醜い数になるという性質を利用し、3つのポインタ（i2、i3、i5）が「2倍」「3倍」「5倍」の候補をそれぞれ追跡します。ループごとに3つの候補の中で最小の値を次の醜い数として採用することで、重複なく小さい順に醜い数を生成できます。

C++による実装例

# include<iostream>
using namespace std;

int min(int x, int y, int z) {          //3つの数の中で最小値を求める
    if(x < y) {
        if(x < z)
            return x;
        else
            return z;
    }else {
        if(y < z)
            return y;
        else
            return z;
    }
}

int getUglyNum(int n) {
    int uglyNum[n];         // 醜い数を格納する配列
    int i2 = 0, i3 = 0, i5 = 0;

    // 次の倍数を 1*2、1*3、1*5 として初期化

    int next2mul = 2;
    int next3mul = 3;
    int next5mul = 5;
    int next = 1;           // 最初の醜い数は1

    uglyNum[0] = 1;

    for (int i=1; i<n; i++) {
        next = min(next2mul, next3mul, next5mul);   // 次の醜い数を求める
        uglyNum[i] = next;

        if (next == next2mul) {
            i2++;           // 因数が2である醜い数のイテレータを進める
            next2mul = uglyNum[i2]*2;
        }

        if (next == next3mul) {
            i3++;           // 因数が3である醜い数のイテレータを進める
            next3mul = uglyNum[i3]*3;
        }

        if (next == next5mul) {
            i5++;           // 因数が5である醜い数のイテレータを進める
            next5mul = uglyNum[i5]*5;
        }
    }
    return next;        // n番目の醜い数
}

int main() {
    int n;
    cout << "Enter term: "; cin >> n;
    cout << n << "th Ugly number is: " << getUglyNum(n) << endl;
}

実行結果

Enter term: 10
10th Ugly number is: 12

このように、項番号として10を入力すると、10番目の醜い数である12が出力されます。全ての醜い数を順番に調べる総当たり方式と比べ、この手法はO(n)の計算量で済むため、大きなnに対しても高速に動作するのが特徴です。