import java.math.BigInteger;
import java.util.*;

public class Euler574 {

    static List<Integer> primesUpTo(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        if (n >= 0)
            isPrime[0] = false;
        if (n >= 1)
            isPrime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i)
                    isPrime[j] = false;
            }
        }
        List<Integer> ps = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i])
                ps.add(i);
        }
        return ps;
    }

    static class DivInfo {
        BigInteger D;
        BigInteger E;
        BigInteger invD;

        DivInfo(BigInteger D, BigInteger E, BigInteger invD) {
            this.D = D;
            this.E = E;
            this.invD = invD;
        }
    }

    static List<DivInfo> buildDivisors(List<Integer> primesLtQ) {
        BigInteger P = BigInteger.ONE;
        for (int r : primesLtQ)
            P = P.multiply(BigInteger.valueOf(r));

        List<BigInteger> divs = new ArrayList<>();
        divs.add(BigInteger.ONE);

        for (int r : primesLtQ) {
            int sz = divs.size();
            BigInteger br = BigInteger.valueOf(r);
            for (int i = 0; i < sz; i++) {
                divs.add(divs.get(i).multiply(br));
            }
        }

        List<DivInfo> out = new ArrayList<>(divs.size());
        for (BigInteger D : divs) {
            BigInteger E = P.divide(D);
            BigInteger invD = E.compareTo(BigInteger.ONE) > 0 ? D.remainder(E).modInverse(E) : BigInteger.ZERO;
            out.add(new DivInfo(D, E, invD));
        }
        return out;
    }

    static BigInteger vOfPrime(int p, List<Integer> primesLtQ, List<DivInfo> divs) {
        BigInteger P = BigInteger.ONE;
        for (int r : primesLtQ)
            P = P.multiply(BigInteger.valueOf(r));

        BigInteger best = null;
        BigInteger half = BigInteger.valueOf((p + 1) / 2);
        BigInteger bp = BigInteger.valueOf(p);

        for (DivInfo di : divs) {
            BigInteger D = di.D;
            BigInteger E = di.E;
            BigInteger A0;

            if (E.compareTo(BigInteger.ONE) == 0) {
                A0 = BigInteger.ZERO;
            } else {
                BigInteger t = bp.remainder(E).multiply(di.invD).remainder(E);
                A0 = D.multiply(t);
            }

            BigInteger As = A0;
            if (As.compareTo(half) < 0) {
                BigInteger need = half.subtract(As);
                BigInteger k = need.add(P).subtract(BigInteger.ONE).divide(P);
                As = As.add(k.multiply(P));
            }
            if (As.compareTo(bp) < 0) {
                if (best == null || As.compareTo(best) < 0)
                    best = As;
            }

            BigInteger A = A0;
            if (A.compareTo(bp) <= 0) {
                BigInteger k = bp.subtract(A).divide(P).add(BigInteger.ONE);
                A = A.add(k.multiply(P));
            }
            if (A.remainder(bp).equals(BigInteger.ZERO)) {
                A = A.add(P);
            }
            if (best == null || A.compareTo(best) < 0)
                best = A;
        }
        return best;
    }

    public static String solve() {
        int n = 3800;
        List<Integer> primes = primesUpTo(n);
        List<Integer> allPrimes = primesUpTo(5000);

        Map<Integer, List<DivInfo>> cacheDivs = new HashMap<>();
        Map<Integer, List<Integer>> cachePrimes = new HashMap<>();

        BigInteger sum = BigInteger.ZERO;

        for (int p : primes) {
            int q = 0;
            for (int r : allPrimes) {
                if (r * r > p) {
                    q = r;
                    break;
                }
            }

            if (!cachePrimes.containsKey(q)) {
                List<Integer> pLtQ = new ArrayList<>();
                for (int r : allPrimes) {
                    if (r >= q)
                        break;
                    pLtQ.add(r);
                }
                cachePrimes.put(q, pLtQ);
                cacheDivs.put(q, buildDivisors(pLtQ));
            }

            sum = sum.add(vOfPrime(p, cachePrimes.get(q), cacheDivs.get(q)));
        }

        return sum.toString();
    }

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