public class Euler386 {
    static String solve() {
        int n = 100000000;
        int[] minDivisor = new int[n + 1];
        minDivisor[1] = 1;

        int limit = (int) Math.sqrt(n);
        for (int i = 2; i <= limit; i++) {
            if (minDivisor[i] == 0) {
                for (int j = i * i; j <= n; j += i) {
                    if (minDivisor[j] == 0) {
                        minDivisor[j] = i;
                    }
                }
            }
        }
        for (int i = 2; i <= n; i++) {
            if (minDivisor[i] == 0) {
                minDivisor[i] = i;
            }
        }

        byte[] degs = new byte[n + 1];
        int[] counts = new int[32];
        degs[1] = 0;
        counts[0] = 1;

        for (int i = 2; i <= n; i++) {
            int reduced = i / minDivisor[i];
            byte d = (byte) (degs[reduced] + 1);
            degs[i] = d;
            counts[d]++;
        }

        int[][] byDegs = new int[32][];
        for (int i = 0; i < 32; i++) {
            byDegs[i] = new int[counts[i]];
        }

        int[] ptrs = new int[32];
        for (int i = 1; i <= n; i++) {
            int d = degs[i];
            byDegs[d][ptrs[d]++] = i;
        }

        long ans = 0;
        for (int i = 0; i < 31; i++) {
            int[] cur = byDegs[i];
            if (cur == null || cur.length == 0)
                continue;

            int low = 0;
            int high = cur.length - 1;
            while (low < cur.length) {
                while (high >= 0 && (long) cur[high] * cur[low] > n) {
                    high--;
                }
                ans += high + 1;
                low++;
            }

            int[] nxt = byDegs[i + 1];
            if (nxt == null || nxt.length == 0)
                continue;

            low = 0;
            high = nxt.length - 1;
            while (low < cur.length) {
                while (high >= 0 && (long) nxt[high] * cur[low] > n) {
                    high--;
                }
                ans += high + 1;
                low++;
            }
        }

        return Long.toString(ans);
    }

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