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

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