Ugly Numbers

来源：cc150, fgdsb

原帖：http://www.hawstein.com/posts/ctci-ch10-math.html
            http://www.fgdsb.com/2015/01/03/ugly-numbers/

题目：
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly numbers. By convention, 1 is included.

Write a program to find and print the 150’th ugly number.

cc150上也有相类似的题目，不过prime factors是3,5,7。

代码：

 int uglyNumber(int n) {  
   vector<int> num(n+1);  
   num[0] = 1;  
   int i3 = 0, i5 = 0, i7 = 0;  
   for (int i = 1; i <= n; ++i) {  
     int next = min({num[i3]*3, num[i5]*5, num[i7]*7});  
     num[i] = next;  
     if (next == num[i3]*3) i3++;  
     else if (next == num[i5]*5) i5++;  
     else i7++;  
   }  
   return num[n];  
 }  
   
 int main() {  
   vector<int> ugly = {1,3,5,7,9,15,21,25,27,35,45,49,63};  
   int k = 5;  
   cout << uglyNumber(k) << endl;  
   return 0;  
 }