ACM: 136 – Ugly Numbers

Ugly number 是質因數只有2或3或5的數字。這題要找出第1500個ugly number。

原本只是單純的一個數字一個數字檢查質因數，直到找到第1500個ugly number為止，但雖然可以找到正確答案，卻會花很久的時間。查了一下討論區，才恍然大悟可以直接用2,3,5去生成倍數，也想出來了生成的方法，真開心！

 

CODE

#include <iostream>

#include <climits>

int main(){

    int u[1500], p[3] = {2, 3, 5};

    int i, j, k, t;

    u[0] = 1;

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

        u[i] = INT_MAX;

        for(j=0; j<3; ++j){

            for(k=0; (t = u[k] * p[j]) <= u[i-1]; ++k);

            if( t < u[i] )

                u[i] = t;

        }//j: 2,3,5

    }//i: i'th ugly number

    printf("The 1500'th ugly number is %d.\n", u[i-1]);

    return 0;

}

 

CODE (naive and slow version)

#include <iostream>

using namespace std;

bool otherprime(int n){

  while( n%2 == 0 )

    n /= 2;

  while( n%3 == 0 )

    n /= 3;

  while( n%5 == 0 )

    n /= 5;

  if( n == 1 )

    return false;

  return true;

}

int main() {

  int n = 1; //start from 2

  int count = 1; //the 1st ugly number is 1

  while( count < 1500 ){ 

    ++n;

    if( (n % 2 == 0) || (n % 3 == 0) || (n % 5 == 0) ){

      if( !otherprime(n) )

        ++count;

    }

  }

  cout << n << endl;

  return 0;

}