//也可以用dfs
public class Main {
    static int cnt;
    static int[] pr = new int[2020];
    static boolean[] st = new boolean[2020];

    //埃氏筛(所有质数的倍数删掉)
    public static void find(int n) {
        for (int i = 2; i <= n; i++) {
            if (!st[i]) {
                pr[cnt++] = i;
                for (int j = 2 * i; j <= n; j += i) {
                    st[j] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        int n = 2019;
        find(n);

        //DP数组 dp[i][j]dp[i][j]的含义为在前i个质数中，能组成j的最大方法数

        long[][] dp = new long[cnt + 1][n + 1];

        // 一个都不选 构成0 的方案数为1
        dp[0][0] = 1;
        for (int i = 1; i <= cnt; i++) {
            for (int j = 0; j <= n; j++) {

                if(j < pr[i - 1]) {
                  //不能组成j，则“继承”上一个的方法数
                  dp[i][j] = dp[i - 1][j];
                }else {
                  //能组成j, 选还是不选这个数
                  dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j] + dp[i - 1][j - pr[i - 1]]);
                }
            }
        }
        System.out.println(dp[cnt][2019]);
    }
}