JavaでN番目のアグリーナンバー（醜い数）を求める方法

アグリーナンバー（Ugly Number）とは？

素因数が2、3、5のいずれかのみである数を「アグリーナンバー（醜い数）」と呼びます。アグリーナンバーには、1, 2, 3, 4, 5, 6, 8, 10, 12, 15などが含まれます。

この問題では、数値Nが与えられ、アグリーナンバーの列の中からN番目の数を求めることが課題となります。

入出力例1

入力：

N = 5

出力：

5

解説：
アグリーナンバーの列 [1, 2, 3, 4, 5, 6, 8, 10, 12, 15] のうち、5番目に位置する数は 5 です。

入出力例2

入力：

N = 7

出力：

8

解説：
同じ列の中で7番目に位置する数は 8 です。

問題を解くためのアプローチ

最もシンプルな解法は、各数値が2・3・5のいずれかで割り切れるかどうかを順番に判定し、条件を満たす数をカウントしながらN番目に到達するまで処理を続けるというものです。アグリーナンバーの条件をすべて満たす数が見つかった時点で、その数を出力として返します。

• N番目のアグリーナンバーを求めるために、数値Nを入力として受け取ります。
• ブーリアン型の関数 isUglyNumber(int num) は、受け取った数がアグリーナンバーであれば true を、そうでなければ false を返します。
• 整数型の関数 nthUglyNumber(int n) は、n番目のアグリーナンバーを計算し、結果として返します。

Javaでの実装例

public class UglyN {
    public static boolean isUglyNumber(int num) {
        boolean x = true;
        while (num != 1) {
            if (num % 5 == 0) {
                num /= 5;
            }
            else if (num % 3 == 0) {
                num /= 3;
            }
            // 数が2で割り切れるかどうかを判定
            else if (num % 2 == 0) {
                num /= 2;
            }
            else {
                x = false;
                break;
            }
        }
        return x;
    }
    public static int nthUglyNumber(int n) {
        int i = 1;
        int count = 1;
        while (n > count) {
            i++;
            if (isUglyNumber(i)) {
                count++;
            }
        }
        return i;
    }
    public static void main(String[] args) {
        int number = 100;
        int no = nthUglyNumber(number);
        System.out.println("The Ugly no. at position " + number + " is " + no);
    }
}

実行結果

The Ugly no. at position 100 is 1536.

計算量に関する補足

この実装では、1から順に各数値がアグリーナンバーかどうかを一つずつ判定しているため、Nが大きくなるほど処理時間が増加します。より高速な手法としては、動的計画法（DP）を用いてアグリーナンバーの列を直接生成するアプローチが知られており、大量の数を扱う場合に有効です。