## [ACM_ZJUT_1089]Ugly Numbers

### Ugly Numbers

Time Limit:1000MS  Memory Limit:32768K

#### Description

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 n’th ugly number.

#### Input

Every integer number (≤1500)describing position of ugly number from 1.If integer number is 0,the process should ended. Maybe there are 10000 integer numbers on input data.

#### Output

Every integer given should output a line as shown below, The <n>th ugly number is <number>. with <n> replaced by the integer number and <number> replaced by the number computed.

```5 16
```

#### Sample Output

```The 5th ugly number is 5.The 16th ugly number is 25.
```

#### Source

ZJUT1089

```#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;
}
```

```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
```

```#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int ugly[1501];
ugly[1] = 1;
int x2 = 1, x3 = 1, x5 = 1, num, n;
for(int i = 2; i < 1501; ++i){
num = min(min(ugly[x2] * 2, ugly[x3] * 3), ugly[x5] * 5);
if(num == ugly[x2] * 2)
++x2;
if(num == ugly[x3] * 3)
++x3;
if(num == ugly[x5] * 5)
++x5;
ugly[i] = num;
}
while(cin >> n){
cout << "The " << n << "th ugly number is " << ugly[n] << "." << endl;
}
return 0;
}
```