Ugly Numbers

n=2^i*3^j*5^k，ijk是自然数。可以得到n序列 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

求此序列第N个数是多少。

一般的人会这样：
把可能的数都算出来，去重，再排序，得到序列
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int main()
{
    set<int> s;
    s.insert(1);
    set<int>::iterator it = s.begin();
    //此处使用1600而非1500，是为了防止类似*it*5 > *(++it)*2的情况出现而导致循环结束时较小的丑数仍未插入容器
    while(s.size()<=1600)
    {
        s.insert(*it*2);
        s.insert(*it*3);
        s.insert(*it*5);
        it++;
    }
    int n;
    while(cin>>n&&n)
    {
        it = s.begin();
        int i = n;
        while(--i){
            ++it;
        }
        cout<<"The "<<n<<"th ugly number is "<<*it<<"."<<endl;
    }
    return 0;
}

明白一些的人思路是这个：http://online-judge.uva.es/board/viewto … mp;t=26972
引用原文代码是：

数小还可以，数大了就会很慢了

然后算法更精一些的人还可以这样：http://www.2cto.com/kf/201306/222203.html
引用原文代码是：

算法思路就是先定义一个集合，该集合中有元素1，如果x在集合中，并且y是x的下一个丑数，那么x*2，x*3，x*5也在集合中，其它数不再集合中，这三个数中必定是2x最小，因此首先放入数组中，而此时*2最小的应该是x的下一个丑数y*2，此时应该找出y*2，x*3，x*5中最小的数放入数组，以此类推，具体操作如下：

1
*2
*3
*5
选出乘积最小的，加入到结果集中，相应指针右移

1     2
*3   *2
*5
选出乘积最小的，加入到结果集中，相应指针右移

1     2     3
*5   *2
*3
选出乘积最小的，加入到结果集中，相应指针右移

1     2     3     4
*5   *3    *2
选出乘积最小的，加入到结果集中，相应指针右移

1     2     3     4
*3   *2
*5
以此类推，直到获得足够长的结果集
嗯。算是空间换时间吧。目的下标不确定的话需要自己处理数组空间。不过速度与前者比较那是相当的快啊。
不知道还有没有更好的解法。