# Ugly Numbers

 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 17500 Accepted: 7757

Description

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, …
shows the first 10 ugly numbers. By convention, 1 is included.
Given the integer n,write a program to find and print the n’th ugly number.

Input

Each line of the input contains a postisive integer n (n <= 1500).Input is terminated by a line with n=0.

Output

For each line, output the n’th ugly number .:Don’t deal with the line with n=0.

Sample Input

```1
2
9
0```

Sample Output

```1
2
10```

Source

```#include <stdio.h>
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;
}```
 Result Memory Time Language Code Length Accepted 172K 0MS C++ 661B

Tonitech版权所有 | 转载请注明出处： http://www.tonitech.com/1785.html