Contents

UVa 443 Humble Numbers


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:

ArraryDescription
anumbers of each prime factors which are used to generate humble numbers
numstore the 4 humble numbers and find the smallest one to fill into the ans array
ansstore 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;
}