UVa 443 - Humble Numbers

// UVa 443 - Humble Numbers

#include <iostream>
#include <map>
#include <queue>
#include <string>
using namespace std;

#define integer unsigned long long

struct humble {
	integer h;
};

bool operator <(humble a, humble b) {
	return a.h > b.h;
}

int main() {
	map<integer, bool> yet;
	integer sol[5843];
	priority_queue<humble> q;
	humble one = { 1 };
	q.push(one);
	for (int i = 1; i <= 5842; i++) {
		integer now = q.top().h;
		sol[i] = now;
		q.pop();
		integer next = now * 2;
		if (!yet[next]) {
			yet[next] = true;
			humble humb = { next };
			q.push(humb);
		}
		next = now * 3;
		if (!yet[next]) {
			yet[next] = true;
			humble humb = { next };
			q.push(humb);
		}
		next = now * 5;
		if (!yet[next]) {
			yet[next] = true;
			humble humb = { next };
			q.push(humb);
		}
		next = now * 7;
		if (!yet[next]) {
			yet[next] = true;
			humble humb = { next };
			q.push(humb);
		}
	}

	int n;
	while ((cin >> n) && n) {
		int m = n % 10;
		string suffix = "th";
		switch (m) {
		case 1:
			suffix = "st";
			break;
		case 2:
			suffix = "nd";
			break;
		case 3:
			suffix = "rd";
			break;
		}
		if (n % 100 == 11 || n % 100 == 12 || n % 100 == 13)
			suffix = "th";
		cout << "The " << n << suffix << " humble number is " << sol[n] << ".\n";
	}
	return 0;
}