【编程基础】丑数

题目描述

素因子都在集合{2 3 5 7}的数称为ugly number
求第n大的丑数

输入

读入N。N<=100000

输出

输出结果如题所述。

样例输入 复制

12

样例输出 复制

15

提示

50%的数据n<=100

100%的数据 n<=100000

AC代码：

#include<bits/stdc++.h>
using namespace std;
int IsUgly( int number ) {
	while ( number % 2 == 0 )
		number /= 2;
	while ( number % 3 == 0 )
		number /= 3;
	while ( number % 5 == 0)
		number /= 5;

	return (number == 1) ? true : false;
}
int GetUglyNumber( int index ) {
	if (index <= 0)
		return 0;

	int number = 0;
	int uglyFound = 1;
	while (uglyFound < index) {
		++number;
		if (IsUgly(number)) {
			++uglyFound;
		}
	}
	return number;
}
int n;
int main() {
	cin >> n;
	printf("%d\n", GetUglyNumber(n));
	return 0;
}