136: ugly numbers

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;
}