#include <iostream>
#include <vector>
#include <set>

#include <boost/date_time/local_time/local_time.hpp>

typedef unsigned int UInt32;
typedef double Float64;
#define CVector std::vector

using namespace std;

// Timer class
class CTimer
{
public:

    // Starts (or restarts) the timer
    void start() { m_start = now(); }

    // Gets the timer elapsed time
    Float64 getElapsedTimeInSeconds()
	{
		const auto dur = now() - m_start;
		return (Float64)dur.total_milliseconds() * 1e-3;
	}

private:

	// Returns the current system time
	static boost::posix_time::ptime now()
	{
		return boost::posix_time::microsec_clock::local_time();
	}

	boost::posix_time::ptime m_start;

};

// brute force
UInt32 nextFactorizationOf1(const UInt32 target, const CVector<UInt32>& primes)
{
	const size_t size = primes.size();
	UInt32 x = target;
	while (x < target * 2)
	{
		const UInt32 y = x;
		for(size_t i = 0; i < size && x > 1; ++i)
		{
			while(x % primes[i] == 0)
			{
				x /= primes[i];
			}
		}

		if (x == 1) return y;
		x = y + 1;
	}
	return 0;
}

// provided by dasblinkenlight
UInt32 nextFactorizationOf2(const UInt32 target, const CVector<UInt32>& primes)
{
	set<UInt32> s;
	s.insert(1);
	UInt32 best = 2 * target;
	UInt32 i = 1;
	while (true)
	{
		set<UInt32> next(s.begin(), s.end());
		for (auto n : s)
		{
			for (auto p : primes)
			{
				UInt32 x = n * p;
				if (x < best) next.insert(x);
			}
		}

		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;
	}
	return best;
}

// provided by anatolyg
UInt32 nextFactorizationOf3(const UInt32 target, const CVector<UInt32>& primes, UInt32 product=1)
{
    if (product >= target) return product;

	UInt32 ret = target * 2;
    for (auto prime : primes)
	{
        ret = min(ret, nextFactorizationOf3(target, primes, product * prime));
	}
	return ret;
}

// provided by Ivan Gritsenko
UInt32 nextFactorizationOf4(const UInt32 target, const CVector<UInt32>& primes)
{
	// initialize bestCandidate as a power of some prime greater than num
	UInt32 bestCandidate = 1;
	while (bestCandidate < target) bestCandidate *= primes[0];

	set<UInt32> s;
	s.insert(1);
	while (!s.empty())
	{
		UInt32 current = *s.begin();
		s.erase(s.begin());

		for (auto p : primes)
		{
			UInt32 newCandidate = current * p;
			if (newCandidate < target)
			{
				// new lower candidates should be stored.
				if (s.find(newCandidate) == s.end()) s.insert(newCandidate);
			}
			else
			{
				if (newCandidate < bestCandidate) bestCandidate = newCandidate;
				break; // further iterations will generate only larger numbers
			}
		}
	}
	return bestCandidate;
}

// utility function to help "fool" the compiler
bool validate(const CVector<UInt32>& results)
{
	const size_t size = results.size();
	for (size_t i = 1; i < size; ++i)
	{
		if (results[i] != results[0]) return false;
	}
	return true;
}

// Note: The results do not need to be stored in a vector or validated,
//       that is simply done to help "fool" the compiler so that certain
//       optimizations do not occur that would affect the timing results
int main() {
	CTimer timer;
	const CVector<UInt32> primes = { 2, 3, 5, 7 };
	const CVector<UInt32> tests = { 5917, 8192, 262145 };
	const size_t iterations = 50;
	CVector<UInt32> results(iterations);

	for (const auto num : tests)
	{
		timer.start();
		for (size_t i = 0; i < iterations; ++i) results[i] = nextFactorizationOf1(num, primes);
		const Float64 elapsed1 = timer.getElapsedTimeInSeconds();
		const UInt32 result1 = results[0];
		if (!validate(results)) cout << endl << "Failure!";

		timer.start();
		for (size_t i = 0; i < iterations; ++i) results[i] = nextFactorizationOf2(num, primes);
		const Float64 elapsed2 = timer.getElapsedTimeInSeconds();
		const UInt32 result2 = results[0];
		if (!validate(results)) cout << endl << "Failure!";

		timer.start();
		for (size_t i = 0; i < iterations; ++i) results[i] = nextFactorizationOf3(num, primes);
		const Float64 elapsed3 = timer.getElapsedTimeInSeconds();
		const UInt32 result3 = results[0];
		if (!validate(results)) cout << endl << "Failure!";

		timer.start();
		for (size_t i = 0; i < iterations; ++i) results[i] = nextFactorizationOf4(num, primes);
		const Float64 elapsed4 = timer.getElapsedTimeInSeconds();
		const UInt32 result4 = results[0];
		if (!validate(results)) cout << endl << "Failure!";

		cout << endl << "Results for " << num << ":"
			 << endl << result1 << " in " << elapsed1 << " s."
			 << endl << result2 << " in " << elapsed2 << " s."
			 << endl << result3 << " in " << elapsed3 << " s."
			 << endl << result4 << " in " << elapsed4 << " s."
			 << endl;
	}
	cout << "Press [ENTER] to exit..." << flush;
	cin.ignore(1);

	return 0;
}