/*
Subject: #136 Ugly Numbers
e-mail: morcavon@gmail.com
Homepage: http://www.morcavon.com
Building: 22/03/2005 ~ 22/03/2005
Last Update: 23/03/2005
*/
/*
<INPUT>
there is no input.
-
<OUTPUT>
The 1500'th ugly number is <number>.
-
<PROBLEM>
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.
*/
#include <iostream>
using namespace std;
#define STOP 1500
//#define ONLINE_JUDGE
bool prime2(unsigned int n);
int main()
{
register short step;
register unsigned int n;
// =_=;;; 이...이것은...
// cout << "The 1500'th ugly number is 859963392.\n";
for (step = 1, n = 2; step < STOP; n++) {
if (prime2(n)) {
step++;
#ifndef ONLINE_JUDGE
cout << "count = " << step << ", " << n << endl;
#endif
}
}
cout << "The 1500'th ugly number is " << n-1 << ".\n";
#ifndef ONLINE_JUDGE
cin.get();
#endif
return 0;
}
bool prime2(unsigned int n)
{
register unsigned short t;
while (n > 6) {
if ((n & 0x01) == 0x00) { // 2로 나눠떨어질때
n >>= 1;
}
else if (n % 3 == 0) { // 3으로 나눠떨어질때
n /= 3;
}
else if ((t = short(n % 10)) == 0 || t == 5) { // 5로 나눠떨어질때
// t = n % 10, 1의 자리를 떼어냄.
n /= 5;
}
else
break;
}
return (n <= 6);
}
