丑数

题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

 1 /**
 2  * 
 3  * @author gentleKay
 4  * 题目描述
 5  * 把只包含质因子2、3和5的数称作丑数（Ugly Number）。
 6  * 例如6、8都是丑数，但14不是，因为它包含质因子7。 
 7  * 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 8  */
 9 
10 public class Main33 {
11 
12     public static void main(String[] args) {
13         // TODO Auto-generated method stub
14         int num = Main33.GetUglyNumber_Solution(12);
15         System.out.println(num);
16     }
17     
18     public static int GetUglyNumber_Solution(int index) {
19         if (index == 0) {
20             return 0;
21         }
22         int count = 1;
23         int[] a = new int[index];
24         a[0] = 1;
25         int index2 = 0;
26         int index3 = 0;
27         int index5 = 0;
28         while (count < index) {
29             int    min = min(a[index2]*2, a[index3]*3, a[index5]*5);
30             a[count] = min;
31             while (a[index2]*2 <= a[count]) {
32                 index2++;
33             }
34             while (a[index3]*3 <= a[count]) {
35                 index3++;
36             }
37             while (a[index5]*5 <= a[count]) {
38                 index5++;
39             }
40             count++;
41         }
42         int result = a[index-1];
43         return result;
44     }
45     
46     public static int min(int a, int b, int c) {
47         int temp = a > b ? b : a;
48         return temp > c ? c : temp;
49     }
50 
51 }