C++ :

#include <bits/stdc++.h>
using namespace std;
int ans=0,tot=0;
int prime(int x)
{
	if (x == 1) return 0;
	for (int i=2;i<=sqrt(x);i++)
	   if (x % i == 0) return 0;
	return 1;
}
void dfs(int x,int s)
{
	if (x <= 1) {
		if (!x) ans = max(ans,tot);
		return;
	}
	for (int i=s+1;i<=x;i++){
		tot++;
		if (prime(i)) dfs(x-i,i);
		tot--;
	}
	
}
int main()
{
	int n;
	cin >> n;
	dfs(n,1);
	cout << ans;
	return 0;
}