You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
67 lines
1.6 KiB
67 lines
1.6 KiB
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
//求第N个丑数
|
|
|
|
//判断素数
|
|
bool isPrime(int n) {
|
|
for (int i = 2; i <= n / i; i++)
|
|
if (n % i == 0) return false;
|
|
return true;
|
|
}
|
|
|
|
//分解质因数
|
|
const int N = 6000;
|
|
int a[N];
|
|
void divide(int n) {
|
|
int k = 0;
|
|
for (int i = 2; i <= n; i++) {
|
|
//为了多次获取同一个质因子
|
|
while (isPrime(i) && n % i == 0) {
|
|
a[k++] = i;
|
|
n /= i;
|
|
}
|
|
}
|
|
}
|
|
|
|
//获取英文中的数字后缀
|
|
//规则说明:https://www.zybang.com/question/771ce4fda2feca20c2dffe7aa11d8dc1.html
|
|
string getNumSuffix(int n) {
|
|
if (n == 1) return "st";
|
|
else if (n == 2) return "nd";
|
|
else if (n == 3) return "rd";
|
|
else if (n >= 4 && n <= 19) return "th";
|
|
else if (n == 21) return "st";
|
|
else if (n == 22) return "nd";
|
|
else if (n == 23) return "rd";
|
|
else return "th";
|
|
}
|
|
|
|
//预处理出丑数的序列
|
|
int choushu[N];
|
|
|
|
//动态规划法
|
|
int nthUglyNumber() {
|
|
choushu[1] = 1;
|
|
int a = 1, b = 1, c = 1, d = 1;
|
|
for (int i = 2; i < N; i++) {
|
|
int n2 = choushu[a] * 2, n3 = choushu[b] * 3, n5 = choushu[c] * 5, n7 = choushu[d] * 7;
|
|
choushu[i] = min(min(min(n2, n3), n5), n7);
|
|
if (choushu[i] == n2) a++;
|
|
if (choushu[i] == n3) b++;
|
|
if (choushu[i] == n5) c++;
|
|
if (choushu[i] == n7) d++;
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
int n;
|
|
//筛出丑数
|
|
nthUglyNumber();
|
|
//接受询问
|
|
while (cin >> n && n) {
|
|
string s = getNumSuffix(n);
|
|
printf("The %d%s humble number is %d.\n", n, s.c_str(), choushu[n]);
|
|
}
|
|
return 0;
|
|
} |