// AddPrimeToN.cpp : アプリケーションのエントリ ポイントを定義します。
//

#include <iostream>
#include <cstdint>
#include <vector>
#include <cmath>
#include <algorithm>

typedef std::vector<std::uint64_t> DType;

//エラトステネスの篩型プライムエンカウンター。

template<class T = std::size_t>
class PrimeEncounterAnother {
public:
	typedef std::vector<bool> PrimeSet;
	typedef T Integer;

	PrimeEncounterAnother() {
		Clear();
	}

	bool Clear() {
		Primes.clear();
		if (Primes.size() == 0) {
			Primes.push_back(true);
			Primes.push_back(true);
			Searched = 1;
		}
		return true;
	}

	bool Search(const Integer& N) {
		if (Searched >= N) return false;
		Integer L = static_cast<Integer>(std::sqrt(N)) + 1;
		Primes.resize(N + 1);
		for (Integer i = 0; i < L; i++) {
			if (Primes[i] == true) continue;
			for (Integer j = (Searched / i) + 1; i*j <= N; j++) {
				if (j <= 1)continue;
				Primes[i*j] = true;
			}
		}
		Searched = N + 1;
		return true;
	}
	Integer IsSearched() {
		return Searched;
	}
	Integer Size() {
		return Primes.size();
	}
	bool operator [](const Integer& Idx) {
		return !Primes[Idx];
	}
protected:
	PrimeSet Primes;
	Integer Searched;
};

std::int64_t MakeHoge(std::uint64_t N) {
	PrimeEncounterAnother<std::uint64_t> P;
	DType D;
	P.Search(N);
	for (std::uint64_t i = 2; i < P.IsSearched(); i++) {
		if (P[i] == true)D.push_back(i);
	}

	std::vector<std::vector<std::int64_t>> DP(D.size()+2);
	for (auto& o : DP) {
		o.resize(N+2);
	}

	for (std::size_t j = 0; j < D.size(); j++) DP[D.size()][j] = 0;

	for (std::int64_t i = D.size()-1; i >= 0; i--) {
		for (std::int64_t j = 0; j <= N; j++) {
			if (j < D[i]) {
				DP[i][j] = DP[i + 1][j];
			}
			else {
				DP[i][j] = std::max(DP[i + 1][j], DP[i + 1][j - D[i]] + 1);
			}
		}
	}


	return DP[0][N];
}

int main()
{
	std::int64_t R;
	R=MakeHoge(2018);
	std::cout << R << std::endl;

    return 0;
}