import java.util.*;

public class Euler343 {

    static long mulMod(long a, long b, long mod) {
        return (long) ((((java.math.BigInteger.valueOf(a)).multiply(java.math.BigInteger.valueOf(b)))
                .remainder(java.math.BigInteger.valueOf(mod))).longValue());
    }

    static long powMod(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = mulMod(result, base, mod);
            }
            base = mulMod(base, base, mod);
            exp >>= 1;
        }
        return result;
    }

    static long tonelliShanks(long n, long p) {
        if (n == 0)
            return 0;
        if (p == 2)
            return n;
        if (powMod(n, (p - 1) / 2, p) != 1)
            return 0;
        if ((p % 4) == 3)
            return powMod(n, (p + 1) / 4, p);

        long q = p - 1;
        int s = 0;
        while ((q % 2) == 0) {
            q /= 2;
            s++;
        }

        long z = 2;
        while (powMod(z, (p - 1) / 2, p) != p - 1) {
            z++;
        }

        long c = powMod(z, q, p);
        long x = powMod(n, (q + 1) / 2, p);
        long t = powMod(n, q, p);
        int m = s;

        while (t != 1) {
            int i = 1;
            long t2i = mulMod(t, t, p);
            while (i < m && t2i != 1) {
                t2i = mulMod(t2i, t2i, p);
                i++;
            }
            long b = powMod(c, 1L << (m - i - 1), p);
            x = mulMod(x, b, p);
            t = mulMod(t, mulMod(b, b, p), p);
            c = mulMod(b, b, p);
            m = i;
        }
        return x;
    }

    static long solve(int limit) {
        int[] lpfSmall = new int[limit + 2];
        List<Integer> primes = new ArrayList<>();

        for (int i = 2; i <= limit + 1; i++) {
            if (lpfSmall[i] == 0) {
                for (int j = i; j <= limit + 1; j += i) {
                    lpfSmall[j] = i;
                }
                if (i <= limit) {
                    primes.add(i);
                }
            }
        }

        long[] rem = new long[limit + 1];
        long[] lpfQ = new long[limit + 1];
        Arrays.fill(lpfQ, 1);

        for (int k = 1; k <= limit; k++) {
            long kk = k;
            rem[k] = kk * kk - kk + 1;
        }

        for (int p : primes) {
            if (p == 2)
                continue;
            List<Integer> roots = new ArrayList<>();
            if (p == 3) {
                roots.add(2);
            } else {
                long mod = p;
                long negThree = (mod + mod - 3) % mod;
                if (powMod(negThree, (mod - 1) / 2, mod) != 1)
                    continue;

                long sq = tonelliShanks(negThree, mod);
                long inv2 = (mod + 1) / 2;
                int r1 = (int) mulMod((1 + sq) % mod, inv2, mod);
                int r2 = (int) mulMod((1 + mod - sq) % mod, inv2, mod);
                roots.add(r1);
                if (r2 != r1) {
                    roots.add(r2);
                }
            }

            for (int root : roots) {
                int k = root;
                if (k == 0)
                    k += p;
                for (; k <= limit; k += p) {
                    long value = rem[k];
                    if (value % p != 0)
                        continue;
                    while (value % p == 0) {
                        value /= p;
                    }
                    rem[k] = value;
                    lpfQ[k] = p;
                }
            }
        }

        long total = 0;
        for (int k = 1; k <= limit; k++) {
            long remVal = rem[k];
            if (remVal > 1) {
                lpfQ[k] = Math.max(lpfQ[k], remVal);
            }
            long lpfKp1 = lpfSmall[k + 1];
            long largest = Math.max(lpfKp1, lpfQ[k]);
            total += (largest - 1);
        }
        return total;
    }

    public static String solve() {
        long ans = solve(2000000);
        return String.valueOf(ans);
    }

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