丑数（C++）

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

数据范围：0≤n≤2000

要求：空间复杂度 O(n)， 时间复杂度 O(n)

输入：
7
返回值：
8

TIPS：

质因子就是质数的因子（因数），该数的所有因子里找质数。

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

正常思路，暴力穷举，但是时间复杂度过大，仅供参考。

class Solution {
  public:
    //是否为质数
    bool IsPrimeNumber(int n) {
        //对n开平方，是因为一个合数n如果有素因子p，则必有另一个因数n/p，p与n/p必有1个小于或等于√n，从而只需要算到平方根即可。
        for (int y = 2; y <= sqrt(n); y++) {
            if (n % y == 0)
                return false;
        }
        return true;
    }

    //是否为丑数(质因数只包含2、3和5)
    bool IsUglyNumber(int n) {
        for (int i = 2; i <= n; i++) {
            //判断是否为丑数
            //先判断其是否为因子（因数），然后在判断是否为丑数所说的质因数，最后判断是否为质数
            if (n % i == 0 && i != 2 && i != 3 && i != 5 && IsPrimeNumber(i))
                return false;
        }
        return true;
    }

    int GetUglyNumber_Solution(int index) {
        vector arrs;
        arrs.push_back(1);
        for (int i = 2;; i++) {
            if (arrs.size() == index)
                break;
            if (IsUglyNumber(i))
                arrs.push_back(i);
        }
        return arrs[index - 1];
    }
};

丑数是任意个2,3,5相乘得到的。
每个丑数都可以乘以一个2,3,5得到一个新的丑数。根据这个思想，我们可以递推出所有的丑数。
首先定义一个数组存储所有的丑数，并从头开始扫描所有丑数，每个丑数都乘以2,3,5，得到新的丑数。所以设三个指针分别表示接下来轮到的那个数乘2,乘3,乘5。
进行index次，即可得到第index个丑数。

class Solution {
  public:
    int GetUglyNumber_Solution(int index) {
        if(!index)return index;
        vector arrs(index + 1,0);
        int p2 = 1,p3 = 1,p5 = 1;
        arrs[1] = 1;
        for(int i = 2;i <= index;i++)
        {
            arrs[i] = min(arrs[p2] * 2,min(arrs[p3]*3,arrs[p5]*5));
            if(arrs[p2] * 2 == arrs[i])p2++;
            if(arrs[p3] * 3 == arrs[i])p3++;
            if(arrs[p5] * 5 == arrs[i])p5++;
        }
        return arrs[index];
    }
};