Ugly Numbers

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, 15, ...

shows the first 11 ugly numbers. By convention, 1 is included.

Write a program to find and print the 1500'th ugly number.

Input and Output

There is no input to this program. Output should consist of a single line as shown below, with <number> replaced by the number computed.

Sample output

The 1500'th ugly number is <number>.

---

#include<stdio.h>
int main() {
    int DP[1500] = {1}, t2 = 0, t3 = 0, t5 = 0, tmp, i;
    for(i = 1; i < 1500; i++) {
        while(DP[t2]*2 <= DP[i-1])    t2++;
        while(DP[t3]*3 <= DP[i-1])    t3++;
        while(DP[t5]*5 <= DP[i-1])    t5++;
        tmp = DP[t2]*2;
        if(DP[t3]*3 < tmp)    tmp = DP[t3]*3;
        if(DP[t5]*5 < tmp)    tmp = DP[t5]*5;
        DP[i] = tmp;
    }
    printf("The 1500'th ugly number is %d.\n", DP[1499]);
    return 0;
}