public class Euler187 {
    public static void main(String[] args) {
        int limit = 100000000, maxQ = (limit - 1) / 2;
        boolean[] sieve = new boolean[maxQ + 1];
        java.util.Arrays.fill(sieve, true);
        sieve[0] = false;
        sieve[1] = false;
        for (int i = 2; (long) i * i <= maxQ; i++)
            if (sieve[i])
                for (int j = i * i; j <= maxQ; j += i)
                    sieve[j] = false;
        int[] primes = new int[maxQ];
        int pc = 0;
        for (int i = 2; i <= maxQ; i++)
            if (sieve[i])
                primes[pc++] = i;
        long count = 0;
        for (int i = 0; i < pc; i++) {
            long p = primes[i];
            if (p * p >= limit)
                break;
            long qmax = (limit - 1) / p;
            int lo = i, hi = pc - 1, ans = i - 1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (primes[mid] <= qmax) {
                    ans = mid;
                    lo = mid + 1;
                } else
                    hi = mid - 1;
            }
            count += ans - i + 1;
        }
        System.out.println(count);
    }
}