import java.util.*;
import java.util.concurrent.*;

public class Euler569 {

    static int mulCmp(long A, long B, long C, long D) {
        long hi1 = Math.multiplyHigh(A, B);
        long lo1 = A * B;
        long hi2 = Math.multiplyHigh(C, D);
        long lo2 = C * D;
        if (hi1 != hi2)
            return hi1 > hi2 ? 1 : -1;
        if (lo1 == lo2)
            return 0;
        return (lo1 + Long.MIN_VALUE > lo2 + Long.MIN_VALUE) ? 1 : -1;
    }

    static boolean slopeLess(long[] x, long[] y, int k, int j1, int j2) {
        long dy1 = y[k] - y[j1];
        long dx1 = x[k] - x[j1];
        long dy2 = y[k] - y[j2];
        long dx2 = x[k] - x[j2];
        return mulCmp(dy1, dx2, dy2, dx1) < 0;
    }

    static boolean crossGe0(long[] x, long[] y, int a, int b, int c) {
        long abx = x[b] - x[a];
        long aby = y[b] - y[a];
        long bcx = x[c] - x[b];
        long bcy = y[c] - y[b];
        return mulCmp(abx, bcy, aby, bcx) >= 0;
    }

    static int[] firstPrimes(int need) {
        int limit = 100000000;
        int half = limit / 2;
        byte[] comp = new byte[half + 1];
        int[] primes = new int[need];
        primes[0] = 2;
        int pCount = 1;

        int sqrtLimit = 10000;
        for (int i = 1; (2 * i + 1) <= sqrtLimit; i++) {
            if (comp[i] == 1)
                continue;
            int p = 2 * i + 1;
            int start = (p * p) / 2;
            for (int j = start; j <= half; j += p) {
                comp[j] = 1;
            }
        }

        for (int i = 1; i <= half && pCount < need; i++) {
            if (comp[i] == 0) {
                primes[pCount++] = 2 * i + 1;
            }
        }
        return primes;
    }

    static class Data {
        long[] x;
        long[] y;
        int[] hullPrev;
    }

    static Data buildData(int N) {
        int need = 2 * N;
        int[] p = firstPrimes(need);

        Data d = new Data();
        d.x = new long[N + 1];
        d.y = new long[N + 1];
        d.hullPrev = new int[N + 1];

        long valleyY = 0;
        long curX = 0;
        for (int k = 1; k <= N; k++) {
            int up = p[2 * k - 2];
            int down = p[2 * k - 1];
            curX += up;
            d.x[k] = curX;
            d.y[k] = valleyY + up;
            curX += down;
            valleyY += (long) up - down;
        }

        int[] st = new int[N];
        int stSz = 0;
        for (int i = 1; i <= N; i++) {
            while (stSz >= 2) {
                int a = st[stSz - 2];
                int b = st[stSz - 1];
                if (crossGe0(d.x, d.y, a, b, i)) {
                    stSz--;
                } else {
                    break;
                }
            }
            d.hullPrev[i] = stSz == 0 ? 0 : st[stSz - 1];
            st[stSz++] = i;
        }
        return d;
    }

    static int P_fast(Data d, int k) {
        if (k <= 1)
            return 0;
        int cnt = 1;
        int best = k - 1;
        int t = best;

        while (t > 1) {
            boolean exists = false;
            for (int v = t - 1; v != 0; v = d.hullPrev[v]) {
                if (slopeLess(d.x, d.y, k, v, best)) {
                    exists = true;
                    break;
                }
            }
            if (!exists)
                break;

            int j = t - 1;
            while (j >= 1 && !slopeLess(d.x, d.y, k, j, best))
                j--;
            if (j <= 0)
                break;

            cnt++;
            best = j;
            t = j;
        }
        return cnt;
    }

    public static String solve() {
        int N = 2500000;
        Data d = buildData(N);

        int threads = Runtime.getRuntime().availableProcessors();
        if (threads <= 0)
            threads = 1;
        ExecutorService executor = Executors.newFixedThreadPool(threads);
        List<Callable<Long>> tasks = new ArrayList<>();

        int start = 1;
        int total = N - start + 1;
        int chunk = (total + threads - 1) / threads;

        for (int ti = 0; ti < threads; ti++) {
            final int L = start + ti * chunk;
            final int R = Math.min(N, L + chunk - 1);
            if (L > R)
                continue;
            tasks.add(() -> {
                long sum = 0;
                for (int k = L; k <= R; k++) {
                    sum += P_fast(d, k);
                }
                return sum;
            });
        }

        long sumP = 0;
        try {
            for (Future<Long> res : executor.invokeAll(tasks)) {
                sumP += res.get();
            }
        } catch (Exception e) {
        }
        executor.shutdown();

        return String.valueOf(sumP);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}