#include <iostream>
#include <set>
#include <vector>
using namespace std;

set<int> expand(const set<int> &current, const vector<int> &primes, int limit) {
	set<int> res(current.begin(), current.end());
	for (auto n : current) {
		for (auto p : primes) {
			int x = n*p;
			if (x < limit) {
				res.insert(x);
			}
		}
	}
	return res;
}

int main() {
	vector<int> primes = { 2, 3, 5, 7 };
	set<int> s;
	s.insert(1);
	int target = 5917;
	int best = 2*5917;
	int i = 1;
	for (;;) {
		set<int> next = expand(s, primes, best);
		if (next.size() == s.size()) {
			break;
		}
		cout << "Generation " << i++ << ", best = " << best << endl;
		for (auto n : next) {
			if (n >= target && n < best) {
				best = n;
			}
		}
		s = next;
	}
	cout << "Best match: " << best << endl;
	return 0;
}