This is a brute force approach. If the current number is divisible by 2, 3 or 5, then divide it by the number it is divisible by. Keep dividing until you reach 1 as long as it is divisible by 2, 3 or 5. If the current dividend is not yet 1, and it is not divisible by 2, 3 or 5, then it means that your current number is not an ugly number. This approach took 26 seconds on an i5 machine. uVA problem specs requires at most 3 seconds. Other blogs discuss using dynamic programming.

#include "stdio.h"

int main() {

int i, x, r, is_ugly, count;

count = 0;

for(i = 1; 1; i += 1) {

x = i;

is_ugly = 1;

while (x > 1) {

r = x % 2;

if (r) {

r = x % 3;

if (r) {

r = x % 5;

if (r) {

is_ugly = 0;

break;

}

else {

x /= 5;

}

}

else {

x /= 3;

}

}

else {

x /= 2;

}

}

if (is_ugly) {

count += 1;

//printf("%d ", i);

if (count >= 1500) {

break;

}

}

}

printf("The 1500'th ugly number is %d.\n", i);

return 0;

}

## No comments:

## Post a Comment