Ugly Number

http://acm.pku.edu.cn/JudgeOnline/problem?id=1338

Description

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, ...
shows the first 10 ugly numbers. By convention, 1 is included.
Given the integer n,write a program to find and print the n'th ugly number.

Input

Each line of the input contains a postisive integer n (n <= 1500).Input is terminated by a line with n=0.

Output

For each line, output the n’th ugly number .:Don’t deal with the line with n=0.

Source

New Zealand 1990 Division I,UVA 136


Solving

Prime factor가 2, 3, 5 만으로 이루어진 수를 ugly number라 한다. n번째 ugly number를 구하라.

방법 1
1부터 모든 수를 검사를 하면서 인수분해를 하여 prime factor가 2, 3, 5 만 있는지 확인하면서 n번째 ugle number를 구한다

방법 2
ugle number의 정의를 이용한다. ugly number는 prime factor가 2, 3, 5만 있기 때문에 반대로 2, 3, 5의 곱으로 이루어진 수를 모두 구해놓은 뒤 소팅을 하여 n번째 ugly number를 구할 수 있다.


#include <cstdlib> #include <cstdio> #include <vector> #include <algorithm> #include <cmath> using namespace std; int m2 = 29; int m3 = 18; int m5 = 12; int main() { int i, j, k; int n; int count = 0; vector<long long> vUgly; for (i = 0; i <= m2; i++) for (j = 0; j <= m3; j++) for (k = 0; k <= m5; k++) vUgly.push_back((long long)pow((double)2,i)*(long long)pow((double)3,j)*(long long)pow((double)5,k)); sort(vUgly.begin(), vUgly.end()); for (i = 0; i < vUgly.size(); i++) if (vUgly[i] > 0) break; vUgly.erase(vUgly.begin(), vUgly.begin()+i); while (scanf("%d", &n) > 0) { if (n == 0) break; printf("%d\n", vUgly[n-1]); } return 0; }