# ZeroJudge - c279: 大家來分解囉~
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=c279
###### tags: `ZeroJudge` `數學` `質數` `動態規劃（Dynamic Programming）`

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define SIZE 20020

int primes[SIZE], primeAmount, DP[SIZE];
bool notPrime[SIZE] = { true, true };

void Initialize() {
	for (int i = 2; i < SIZE; ++i) {
		if (!notPrime[i]) {
			primes[primeAmount] = i;
			++primeAmount;
		}
		for (int j = 0; i * primes[j] < SIZE; ++j) {
			notPrime[i * primes[j]] = true;
			if (!(i % primes[j]))
				break;
		}
	}
	memset(DP, -1, sizeof(DP)); DP[0] = 0;
	for (int i = 0; i < primeAmount; ++i)
		for (int j = SIZE - 1; j >= primes[i]; --j)
			DP[j] = max(DP[j], DP[j - primes[i]] + (DP[j - primes[i]] != -1));
}

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	int number;
	Initialize();
	while (cin >> number)
		cout << DP[number] << '\n';
}