找到第\(n\) \( (1 \le n \le 5842)\) 个只有2,3,5或7质因子的数。

链接: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=384






题解

解法1

有点暴力。。。 用STL setvector来枚举所有符合条件的数。用long long来防止爆int和栈。

#include<iostream>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
const int t[] = { 2, 3, 5, 7};
set<ll> s;

int main(void) {
    s.insert(1);
    set<ll>::iterator i = s.begin();
    while(s.size() < 6600) {
        for (int j = 0; j < 4; j++)
            s.insert((*i)*t[j]);
        i++;
    }
    vector<ll> v(s.begin(), s.end());

    int n;
    string s;
    while (cin >> n) {
        if (n == 0) break;
        if (n % 100 == 11 || n % 100 == 12 || n % 100 == 13) s = "th";
        else if (n % 10 == 1) s = "st";
        else if (n % 10 == 2) s = "nd";
        else if (n % 10 == 3) s = "rd";
        else s = "th";
        cout << "The " << n << s << " humble number is " << v[n-1] << ".\n";
    }
    return 0;
}


解法2

我们有:

数组 描述
a 质因子使用的次数,用来生成下一个数
num 保存4个质因子生成的数, 找到最小的填入ans数组中
ans 打表


每一个humble number \(a\),一定存在一个小于\(a\)的humble number \(b\) 使得\(\lbrace a = kb, k \in \lbrace 2, 3, 5, 7\rbrace \rbrace\)


#include<iostream>
#include<algorithm>
#include<string>
#define maxn 5842+5
using namespace std;
const int t[] = { 2, 3, 5, 7 };
int a[4] = {1, 1, 1, 1}, num[4], n, ans[maxn];
string s;

int find_min() {
    int Min = num[0];
    for (int j = 1; j < 4; j++) {
        if (Min > num[j]) { Min = num[j]; }
    }
    return Min;
}

int main(void) {
    int index = 2;
    ans[1] = 1;
    while(index < maxn) {
        for (int i = 0; i < 4; i++) num[i] = ans[a[i]]*t[i];
        ans[index] = find_min();
        for (int i = 0; i < 4; i++) {
            if (ans[index] == num[i]) a[i]++;
        }
        index++;
    }

    while (cin >> n) {
        if (n == 0) break;

        if (n % 100 == 11 || n % 100 == 12 || n % 100 == 13) s = "th";
        else if (n % 10 == 1) s = "st";
        else if (n % 10 == 2) s = "nd";
        else if (n % 10 == 3) s = "rd";
        else s = "th";
        cout << "The " << n << s << " humble number is " << ans[n] << ".\n";
    }
    return 0;
}