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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #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\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #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;
}
|