程序员面试题精选100题（37）-寻找丑数[算法] (2)

        number /= 3;

    while(number % 5 == 0)

        number /= 5;

 

    return (number == 1) ? true : false;

}

接下来，我们只需要按顺序判断每一个整数是不是丑数，即：

int GetUglyNumber_Solution1(int index)

{

    if(index <= 0)

        return 0;

 

    int number = 0;

    int uglyFound = 0;

    while(uglyFound < index)

    {

        ++number;

 

        if(IsUgly(number))

        {

            ++uglyFound;

        }

    }

 

    return number;

}

我们只需要在函数GetUglyNumber_Solution1中传入参数1500，就能得到第1500个丑数。该算法非常直观，代码也非常简洁，但最大的问题我们每个整数都需要计算。即使一个数字不是丑数，我们还是需要对它做求余数和除法操作。因此该算法的时间效率不是很高。

接下来我们换一种思路来分析这个问题，试图只计算丑数，而不在非丑数的整数上花费时间。根据丑数的定义，丑数应该是另一个丑数乘以2、3或者5的结果（