rt 第二个测试点 N=1000

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int range=2e5+5;
const int MAXN=1e3+10;
int n;
int a[200005];
bool isprime[MAXN]; 
int prime[MAXN];  
int cnt; 
void euler()
{
	//96557227483691514  1005输出的 
	//48278613741845757   1010时
	memset(isprime, true, sizeof(isprime)); // 先全部标记为素数
	isprime[1] = false; // 1不是素数
	for(int i = 2; i <= MAXN; ++i) 
	{
		if(isprime[i]) prime[++cnt] = i;
		for(int j = 1; j <= cnt && i * prime[j] <= MAXN; ++j)
		{
			isprime[i * prime[j]] = false;
			if(i % prime[j] == 0) break;
		}
	}
}
int f[range];
void solve()
{  
	euler();
	int n;
	cin>>n;
	f[0]=1;
	int g=lower_bound(prime+1,prime+1+cnt,n)-prime;
	if(prime[g]>n)g--;
	for(int i=1;i<=g;i++)
	{
		for(int j=prime[i];j<=n;j++)
		{
			f[j]+=f[j-prime[i]];
		}
	}
	cout<<f[n];	
}
signed main()
{
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
	
	
}