C++で醜い数（Ugly Number）を求めるアルゴリズムと実装方法

醜い数（Ugly Number）とは

醜い数（Ugly Number）とは、素因数が2、3、5のみで構成される正の整数のことです。1から15までの範囲には、1、2、3、4、5、6、8、9、10、12、15の合計11個の醜い数が存在します。

一方、7、11、13はそれ自体が素数であるため醜い数には該当しません。また、14は素因数に7を含むため、醜い数とはみなされません。例として、10番目の醜い数を求めると、その値は12になります。

アルゴリズムの考え方

この問題は、3つのインデックス（ポインタ）を使った動的計画法的なアプローチで効率よく解けます。すでに求めた醜い数に対して、それぞれ2倍、3倍、5倍した値のうち最小のものを次の醜い数として採用していく方法です。

アルゴリズム：getUglyNumbers(n)

入力 − 求めたい項数 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, 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

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;
}

入力例

10

出力例

Enter term: 10
10th Ugly number is: 12

計算量について

このアルゴリズムの時間計算量はO(n)、空間計算量もO(n)です。各ステップで候補となる3つの値の中から最小値を選んでいくため、すべての数について素因数分解を総当たりで行う方法と比べてはるかに効率的にn番目の醜い数を求められます。