[Java] UVa 136 Ugly Numbers

題目連結

題意:
uglynumber 代表該數的質因數只包含2, 3, 5，如:8 = 2*2*2 為ugly，21 = 3*7，非ugly
題目沒有input，只要找到第1500個 uglynumber 後輸出即可(定義1為第一個)

我的解法:
一開始我用直觀去想，從2開始分別一直整除以2, 3, 5看最後結果是否為1，發現第1500個數遠遠大於100w，甚至到億，一直沒有想到有什麼比較快的解法

後來還是上網找解法...大部分的人好像都是同一個邏輯，我們不從1開始，而是直接思考 ugly 的定義，至少不是做幾億次，而是1500而已。

剛剛提到ugly是由2, 3, 5質因數相乘而得

既然又是遞增的，所以每一個數勢必都是由之前的某一個數乘以三數其中一個而來。
2 (ugly 2) = 1 (ugly 1) * 2
3 (ugly 3) = 1 (ugly 1) * 3
5 (ugly 4) = 1 (ugly 1) * 3
 ...

因此，定義 3 個index，既然每次的 ugly 都是由某個以前的數乘上2, 3, 5，那就從3個index開始，各找到一個比前一個ugly大的最小的數，再取當中的最小值，就是當前要找的 ugly，同時也記錄三者當前index，下次從這三個index往下找(不可能在它們之前，因為ugly是遞增排列的)。重複進行1500次後，答案呼之欲出，真難倒我了...

參考解法

import java.util.Scanner;

public class Main {
    public static void Main(String[] args) {
        try{
         int[] ugly = new int[1501];
            int m2 = 0, m3 = 0, m5 = 0;
            int tmp = 1; 
            ugly[0] = 1;
            for(int i = 1 ; i < 1500 ; i++){
                for(; m2 < i ;m2++)
                    if( ugly[m2]*2 > tmp)
                        break; 
                for(; m3 < i ;m3++)
                    if( ugly[m3]*3 > tmp)
                        break; 
                for(; m5 < i ;m5++)
                    if( ugly[m5]*5 > tmp)
                        break; 
                tmp = Math.min( ugly[m5] * 5, Math.min( ugly[m2] * 2 ,ugly[m3] * 3) );
                ugly[i] = tmp; 
            }
            
            System.out.println( "The 1500'th ugly number is " + ugly[1499] + ".");
            
        }catch(Exception e){
            System.out.println("Input error!");
        }
    }
};