# Ugly Number II

## 題目

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

## 方法一

### 程式碼

``````class Solution {
public:
int nthUglyNumber(int n) {
int i = 0;
int num = 1;
while (i != n)
{
if (isUgly(num) )
{
i  ;
}
num  ;
}
return num - 1;
}
bool isUgly(int num) {
if (num <= 0)
{
return false;
}
if (1 == num)
{
return true;
}
int pNum = num;
while (pNum % 5 == 0)
{
pNum /= 5;
}
while (pNum % 3 == 0)
{
pNum /= 3;
}
while (pNum % 2 == 0)
{
pNum /= 2;
}
if (pNum == 1)
{
return true;
}
else
{
return false;
}
}
};``````

## 方法二

### 程式碼

``````class Solution {
public:
long nthUglyNumber(int n) {
int i = 1;
set<long> s;
s.insert(1);
while (i < n)
{
long first = *s.begin();
s.insert(first * 2);
s.insert(first * 3);
s.insert(first * 5);
s.erase(first);
i  ;
}
return *s.begin();
}
};``````