【Q136】 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.

　　這題目看似簡單，用直覺的想法莫過於一一檢查其因數是否只有2, 3或5，對於這樣的演算法去run花了109秒。程式如下（或下載）：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int isUgly(int number) ;

int genUgly(int order) ;

int main() {
    time_t start, end ;
    time(&start) ;
        int count = 0 ;
    int i = 0 ;


    while(count < 1500) {
        if(isUgly(++i))
            count++ ;
    }
    printf("%d\n", i) ;
    time(&end) ;
    printf("It takes %.0f seconds!!\n", difftime(end, start)) ;
    system("pause") ;
    return 0 ;
}


int isUgly(int number) {
    while(!(number%2))
        number >>= 1 ;
    while(!(number%3))
        number /= 3 ;
    while(!(number%5))
        number /= 5 ;

    if(number > 1) {
        return 0 ;
    }
        return 1 ;
}

　　這題目的其中要義應該是要解題者想出更有效率的演算法，上面的作法是檢查該數字是不是Ugly Number；另一種想法則是去產生Ugly Number，用這演算法去run時間一秒都不需要，瞬間跑出結果，這也印證了好的演算法與不好的演算法差異是很大的！程式如下（或下載）：

內容：

#include <stdio.h>
#include <stdlib.h>

int number[1500] = {1, 2, 3, 4, 5} ;
int base[3] = {2, 3, 5} ;


int ugly(int order) ;
int genUgly(int count) ;

int main() {
    printf("The 1500'th ugly number is %d.\n", ugly(1500) ) ;
    system("pause") ;
    return 0 ;
}


int ugly(int order) {
    int count = 4 ;
    int temp, i, j ;
    int min ;
    order-- ;
    if(order < 5)
        return number[order] ;
    while(count < order) {
        min = 0 ;
        for(i=0 ; i<count ; i++) {                 
            for(j=0 ; j<3 ; j++) {                 
                temp = number[i]*base[j] ;
                if(temp <= number[count]) {
                    continue ;
                }
                else if(min==0  min > temp) {
                    min = temp ;
                }
            }
        }
        number[++count] = min ;                    
    }
    return number[order] ;
}