# UVa 443 Humble Numbers

Contents

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.

  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 #include #include using namespace std; typedef long long ll; const int t[] = { 2, 3, 5, 7}; set s; int main(void) { s.insert(1); set::iterator i = s.begin(); while(s.size() < 6600) { for (int j = 0; j < 4; j++) s.insert((*i)*t[j]); i++; } vector 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 #include #include #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; }