#include #include using namespace std; // エラトステネスの篩 O(nloglogn) // create p (1<=p<=n and p is a prime nubmer) #define MAX_N 100000 vector prime; bool is_prime[MAX_N + 1]; long long sieve(long long n) { long long p = 0; for (long long i = 0; i <= n; i++) is_prime[i] = true; is_prime[0] = is_prime[1] = false; for (long long i = 2; i <= n; i++) { if (!is_prime[i]) continue; prime.push_back(i); for (long long j = 2 * i; j <= n; j += i) { is_prime[j] = false; } } return p; } int dp[3000][31000]; int main() { for (int i = 0; i < 3000; i++) { for (int j = 0; j < 31000; j++) { dp[i][j] = -1; } } int N; cin >> N; sieve(N); dp[0][0] = 0; for (int i = 0; i < prime.size(); i++) { for (int j = 0; j <= N; j++) { if (dp[i][j] < 0) continue; dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); dp[i + 1][j + prime[i]] = max(dp[i + 1][j + prime[i]], dp[i][j] + 1); } } cout << dp[prime.size()][N] << endl; return 0; }