Find \(n\)th \( (1 \le n \le 5842)\) number whose only prime factors are 2, 3, 5 or 7.

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






Solutions

Solution 1

Kind of brute force, using STL set and vector to list all humble numbers. Using long long to avoiding overflow.

#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;
}


Solution2

We have:

Arrary Description
a numbers of each prime factors which are used to generate humble numbers
num store the 4 humble numbers and find the smallest one to fill into the ans array
ans store all previous results


For every humble number \(a\), there must exist a humble number \(b, b \lt a\) so that \(\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;
}