#include <iostream>
#include <iomanip>
#include <vector>
#include <numeric>
#include <cmath>

namespace Chapter7
{
	class Exercise3
	{
		public:
		void Find(int lo, int hi, std::ostream& out = std::cout);
		
		private:
		std::vector<int> factors_;
		bool IsPrime(int candidate);
		void GetFactors(int candidate);
	};
}

int main() 
{
	Chapter7::Exercise3 solver;
	solver.Find(1, 1000);
}

void Chapter7::Exercise3::Find(int lo, int hi, std::ostream& out)
{
	int sum;
	for (int i = lo; i <= hi; ++i) {
		GetFactors(i);
		sum = std::accumulate(factors_.begin(), factors_.end(), 0);
		if (IsPrime(sum)) {
			out << std::setw(4) << i << ". ";
			if (factors_.size() != 1) {
				std::vector<int>::iterator elem = factors_.begin();
				out << *elem;
				for (++elem; elem < factors_.end(); ++elem) {
					out << " + " << *elem;
				}
				out << " = " << sum;
			}
			out << std::endl;
		}
	}
}

bool Chapter7::Exercise3::IsPrime(int candidate)
{
	if (candidate <= 1) return false; // candidate is not prime by definition
	if (candidate == 2) return true;
	if ((candidate & 1) == 0) return false; // even cadidate
	
	double root = std::sqrt(candidate);
	for (int i = 3; i <= root; i += 2) {
		if (candidate % i == 0) {
			return false;
		}
	}
	return true;
}

void Chapter7::Exercise3::GetFactors(int candidate)
{
	int i = 2;
	factors_.clear();
	while (candidate > 1) {
		while (candidate % i == 0) {
			factors_.push_back(i);
			candidate /= i;
		}
		++i;
	}
}
