- 题目描述：
-
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
- 输入：
-
输入包括一个整数N(1<=N<=1500)。
- 输出：
-
可能有多组测试数据，对于每组数据，
输出第N个丑数。
- 样例输入：
-
3
- 样例输出：
-
3
思路：
常规思路，反复消因子2 3 5，如果最后剩下1，就是丑数，但最后发现超时了。见代码2。
优化的思路跟素数筛法有点类似，参考的别人的代码写的，很巧，学习了！见代码1。
代码1：
#include <stdio.h>
#include <stdlib.h>
int min(int a, int b, int c)
{
int r;
r = a<b ? a : b;
r = r<c ? r : c;
return r;
}
int main()
{
int n, count;
while(scanf("%d", &n) != EOF)
{
int *nums = (int *)malloc(n*sizeof(int));
nums[0] = 1;
count=1;
int *p2 = nums;
int *p3 = nums;
int *p5 = nums;
while (count < n)
{
nums[count] = min(*p2*2, *p3*3, *p5*5);
while (nums[count] >= *p2*2)
p2++;
while (nums[count] >= *p3*3)
p3++;
while (nums[count] >= *p5*5)
p5++;
count ++;
}
printf("%d
", nums[count-1]);
free(nums);
}
return 0;
}
/**************************************************************
Problem: 1214
User: liangrx06
Language: C
Result: Accepted
Time:20 ms
Memory:912 kb
****************************************************************/代码2（原来的超时代码）：
#include <stdio.h>
int main()
{
int n, m, tmp, count;
while(scanf("%d", &n) != EOF)
{
count=1;
m=1;
while (count != n)
{
m++;
tmp = m;
while (tmp % 2 == 0)
tmp /= 2;
while (tmp % 3 == 0)
tmp /= 3;
while (tmp % 5 == 0)
tmp /= 5;
if (tmp == 1)
count ++;
}
printf("%d
", m);
}
return 0;
}
/**************************************************************
Problem: 1214
User: liangrx06
Language: C
Result: Time Limit Exceed
****************************************************************/