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

思路一：直接写个函数挨个判断一下那个数是不是丑数，然后就可以得到第几个丑数是什么了。这种方式比较简单就不上代码了。

思路二：空间换时间，再加上一点技巧，个人感觉有点动态规划的意思：

首先我们分析一下这个面试题的描述，既然所有的数的因子都只有2,3,5，那么我们可以得到每个数必然是前面的数乘2,3,5的最小数，也就是说找到那么一个数是的他是已有的丑数集合中乘以2,3,5的最小数，这个数也就是下一个丑数。但是我们知道不能真的去按集合求（虽然这样铁定是对的，可是复杂度。。。。）。于是我们就要想到一个变通的方法，不难想到对于2,3,5他们肯定是乘以前面的某一个值的时候才会产生所需的数，换句话说：对于2，3，5他们产生的下一个数只与前面的某一个有关。这样我们不难想到记录这个值，然后增加即可。代码如下：

1 #include
      
        2 #include
       
         3  4 long long a[2000]; 5 using namespace std; 6 int main() 7 { 8     int p=0; 9     int q=0;10     int r=0;11     a[0]=1;12     for(int i=1;i<1600;i++)13     {14         a[i]=min(a[p]*2,min(a[q]*3,a[r]*5));15         if(a[p]*2<=a[i])16         p++;17         if(a[q]*3<=a[i])18         q++;19         if(a[r]*5<=a[i])20         r++;21     }22     int N;23     while(scanf("%d",&N)==1)24     {25         printf("%lld\n",a[N-1]);26     }27     return 0;28 }