#include<bits/stdc++.h>
using namespace std;
int b[10000001];
int ans[10000001];
int dp[10000001];
int cnt=0;
int init(int N){
    memset(b,1,sizeof(b));
    b[0]=0;
    b[1]=1;
    for(long long i=2;i<=N;i++){
        if(b[i]){
            for(long long j=2;i*j<=N;j++){
                b[i*j]=0;
            }
        }
    }
    int x;
    for(int i=2;i<=N;i++){
        if(b[i]){
            ans[++x]=i;
        }
    }
    return x;
}
int main(){
    dp[0]=1;
    long long n,m;
    cin>>n;
    int tmp=init(n);
    for(int i=1;i<=tmp;i++){
        for(int j=ans[i];j<=n;j++){
            dp[j]+=dp[j-ans[i]];//Complete-Backpack-Dp
        }
    }
    cout<<dp[n];
    return 0;
}

windows:20 -> 26

洛谷的:20 -> 104