10
// Ugly Numbers
//只能被2,3,5整除，1,2,3,4,5,6,8,9,10...
#include <stdio.h>
//在已知第一个丑数基础上，分别进行*2，*3，*5操作，然后取最小的依次放入数组
//即可避免所有数字暴力穷举选择
int twoNum = 0, threeNum = 0, fiveNum = 0;
int ugly[1500];
void create()
{
ugly[0] = 1;
for (int i = 1; i < 1500; i++) {
int min = ugly[twoNum] * 2, b = ugly[threeNum] * 3, c = ugly[fiveNum] * 5;
if (b < min) {
min = b;
}
if (c < min) {
min = c;
}
ugly[i] = min;
if (ugly[i] == ugly[twoNum] * 2) {
twoNum++;
}
if (ugly[i] == ugly[threeNum] * 3) {
threeNum++;
}
if (ugly[i] == ugly[fiveNum] * 5) {
fiveNum++;
}
}
}
int main()
{
create();
int n;
while (scanf("%d", &n) != EOF) {
if (n == 0) {
return 0;
}
printf("%d\n", ugly[n - 1]);
}
return 0;
}
原文：http://blog.csdn.net/u013240812/article/details/20633229