题目
我们把只包含因子2、3、5的数称为丑数（Ugly Number）。求按照从小到大的顺序的第1500个丑数。例如，6、8都是丑数，但14不是，因为它包含因子7.习惯上我们把1当作第一个丑数。
分析
暴力法
从1开始每个数字都判断，若是丑数，计数器就+1。
前20个丑数为：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36。
C++
#include <iostream> using namespace std; bool IsUglyNum(int n)//判断是否为丑数 { while (n % 2 == 0) { n /= 2; } while (n % 3 == 0) { n /= 3; } while (n % 5 == 0) { n /= 5; } if (n == 1) { return true; } else { return false; } } int GetUglyNumber(int n)//获取第n个丑数 { if (n <= 0) { return -1; } int count = 1; int number = 1;//第一个丑数 for (int i = 2; count < n; i++) { if (IsUglyNum(i) == true) { count++; number = i; cout << i << endl; } } return number; } int main() { int num = GetUglyNumber(10); cout << "第10个丑数是：" << num << endl; return 0; }
测试结果
下图为n=155时的运行时间。36s
为了测试程序的正确性，我们将n=10再测试一遍
规律法
上面验证是否为丑数，是通过整除以2、3、5。那么我们能否通过乘以2、3、5来得出新的丑数呢。
我们创建一个数组ugly，将第一个丑数放进去，然后2用i来标记它自己的进度，同理3用j，5用k。每次取2*ugly[i]、3*ugly[j]、5*ugly[k]三者最小值，并将对应的下标+1，若最小值为多个，多个均+1。
我们举个例子：现在数组内只有{1，0…}。然后取2*ugly[i]、3*ugly[j]、5*ugly[k]小值为2*ugly[i]，我们将值存入数组中。并将i++，数组就有{1,2}。以此类推
C++
#include <iostream> #include <algorithm> using namespace std; int GetUglyNumber(int n)//获取第n个丑数 { if (n <= 0) { return -1; } int* ugly = new int[n]; ugly[0] = 1; int i = 0; int j = 0; int k = 0; for (int index = 1; index < n; index++) { ugly[index] = min(ugly[i] * 2, min(ugly[j] * 3, ugly[k] * 5)); if (ugly[index] == ugly[i] * 2) { i++; } if (ugly[index] == ugly[j] * 3) { j++; } if (ugly[index] == ugly[k] * 5) { k++; } } return ugly[n-1]; } int main() { int num = GetUglyNumber(1500); cout << "第1500个丑数是：" << num << endl; return 0; }
测试结果与暴力法一样
本章完！
