Ugly Numbers
-------------------------------------------
Time limit: 1sec. Submitted: 111
Memory limit: 32M Accepted: 50
Source : UVA - V1
-------------------------------------------
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>
#include <limits.h>
#define MAXN 1500
int n;
unsigned long workarr[1+MAXN] = {0, 1};
int plist[3] = {2, 3, 5};
void InitWorkArr()
{
int i, j, k;
unsigned long min, res;
for (i=2; i<=MAXN; i++)
{
min = 0;
for (j=i-1; workarr[j]*plist[2]>workarr[i-1]; j--)
{
for (k=2; k>=0; k--)
{
res = workarr[j]*plist[k];
if (res <= workarr[i-1])
break;
else if (min == 0 || min > res)
min = res;
}
}
workarr[i] = min;
}
}
int main()
{
int d = 1500;
InitWorkArr();
printf("The %d'th ugly number is %lu./n", d, workarr[d]);
return 0;
}