練習 － Ugly Numbers

Ugly Numbers

題目：醜陋數(ugly number)是僅有質因數2、3或5的整數。序列1,2,3,4,5,6,8,9,10,12,⋯，列出了前10個醜陋數。按照慣例，1被包含在醜陋數中。

輸入：輸入的每行列出一個正整數n（n<=1500)。輸入以n=0的一行結束。

輸出：對於輸入的每一行，輸出第n個醜陋數，對n=0的那一行不作處理並結束。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class UglyNumbers {

	public static void main(String[] args) {
		long limit = 1000000000;
		List<Long> uglyNumbers = new ArrayList<Long>();
		uglyNumbers.add((long) 1);
		for (long i = 1; i < limit; i *= 2) {
			for (long j = 1; i * j < limit; j *= 3) {
				for (long k = 1; i * j * k < limit; k *= 5) {
					uglyNumbers.add((long) i * j * k); // 列出所有少於limit的醜陋數
				}
			}
		}
		Collections.sort(uglyNumbers, new Comparator<Long>() { // 排列醜陋數數組
					@Override
					public int compare(Long o1, Long o2) {
						long result = o1 - o2;
						return (int) result;
					}
				});
		Scanner scanIn = new Scanner(System.in);
		int num = scanIn.nextInt();
		while (num != 0) {
			System.out.printf("%s ugly number: %s \n", num,
					uglyNumbers.get(num));
			scanIn = new Scanner(System.in);
			num = scanIn.nextInt();
		}
	}

}