import std.algorithm.comparison; import std.conv; import std.stdio; import std.string; const int MAX_N = 20000; const int UNDEF = -1; immutable PRIMES = sieveOfEratosthenes(MAX_N); pure @safe int[] sieveOfEratosthenes(const int end){ assert(end > 1); auto isPrime = new bool[](end); isPrime[] = true; isPrime[0] = false; isPrime[1] = false; int[] primes; for (int i = 2; i < end; i++){ if (isPrime[i]){ primes ~= i; for (int j = 2 * i; j < end; j += i){ isPrime[j] = false; } } } return primes; } pure @safe int compute(const int n){ auto dp = new int[](n + 1); dp[] = UNDEF; dp[0] = 0; foreach (prime; PRIMES){ if (prime > n) { break; } for (int i = n - 1; i >= 0; i--) { if (dp[i] != UNDEF && i + prime < n + 1){ dp[i + prime] = max(dp[i + prime], dp[i] + 1); } } } return dp[n]; } void main(){ readln.chomp.to!int.compute.writeln; }