UVa 11752 - The Super Powers

#include <stdio.h>
#include <string.h>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdlib>
using namespace std;

typedef unsigned long long ull;
typedef pair<ull, int> par;

const ull LIMIT = 18446744073709551615ULL; // = 2^64 - 1
const ull TWO_TO_16 = 1 << 16; // = 2^16
const ull TWO_TO_8 = 1 << 8; // = 2^8

ull pow(ull base, int exponent) {
	ull result = 1ULL;
	while (exponent) {
		if (exponent & 1) {
			result *= base;
			exponent ^= 1;
		}
		base *= base;
		exponent >>= 1;
	}
	return result;
}

class CompareCandidate {
public:
	bool operator()(const par & a, const par & b) {
		return pow(a.first, a.second) > pow(b.first, b.second);
	}
};

int main() {

	bool is_power[TWO_TO_16];
	memset(is_power, false, sizeof(is_power));
	for (ull i = 2; i < TWO_TO_8; i++)
		if (!is_power[i]) {
			for (ull j = i * i; j < TWO_TO_16; j *= i)
				is_power[j] = true;
		}

	int max_exponent[TWO_TO_16];
	for (ull i = 2; i < TWO_TO_16; i++)
		if (!is_power[i]) {
			max_exponent[i] = ceil(64 / (log(i) / log(2))) - 1;
		}

	int next_compositive[65], previous = 4;
	for (int i = 6; i <= 65; i++) {
		bool is_compositive = false;
		for (int j = 2; j < i; j++)
			if (i % j == 0) {
				is_compositive = true;
				break;
			}
		if (is_compositive) {
			next_compositive[previous] = i;
			previous = i;
		}
	}

	// add to candidates all x^4 where x is not a power
	priority_queue<par, vector<par>, CompareCandidate> candidates;
	for (ull i = 2; i < TWO_TO_16; i++)
		if (!is_power[i])
			candidates.push(make_pair(i, 4));

	printf("1\n");

	// take smallest candidate x^n, print it, add x^m as candidate where m is next compositive greater than n
	// add x*m as candidate only if m < log(x, MAX)
	while (!candidates.empty()) {
		par candidate = candidates.top();
		candidates.pop();
		printf("%llu\n", pow(candidate.first, candidate.second));

		int m = next_compositive[candidate.second];
		if (m <= max_exponent[candidate.first])
			candidates.push(make_pair(candidate.first, m));
	}

	return 0;
}