1181.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1181 on 2005-09-17 at 11:15:21 */ 
#include <stdio.h>
#define  ORDER  1500

int main()
{
    long long ugly[ORDER], min;
    int i, order = 0, minp;
    int index[3], prime[3] = {2, 3, 5};
    
    for(i = 0; i < 3; i++) {
        index[i] = 0;
    }
    ugly[order++] = 1;
    while(order < ORDER) {
        min = 0x7FFFFFFF;
        for(i = 0; i < 3; i++) {
            while(prime[i] * ugly[index[i]] <= ugly[order-1]) {
                index[i]++;
            }
            if(prime[i] * ugly[index[i]] < min) {
                min = prime[i] * ugly[index[i]];
                minp = i;
            }    
        }
        ugly[order++] = min;
        index[minp]++;
    }
    printf("The 1500'th ugly number is %lld.\n", ugly[ORDER-1]);
    
    return 0;
}