public class Euler216 {
    public static void main(String[] args) {
        int limitN = 50000000;
        long maxT = 2L * limitN * limitN - 1;
        int maxPrime = (int) Math.sqrt(maxT);
        boolean[] sieve = new boolean[maxPrime + 1];
        for (int i = 2; (long) i * i <= maxPrime; i++)
            if (!sieve[i])
                for (int j = i * i; j <= maxPrime; j += i)
                    sieve[j] = true;
        int[] primes = new int[maxPrime / 5];
        int pc = 0;
        for (int p = 2; p <= maxPrime; p++)
            if (!sieve[p])
                primes[pc++] = p;

        boolean[] composite = new boolean[limitN + 1];
        for (int pi = 0; pi < pc; pi++) {
            int p = primes[pi];
            if (p == 2)
                continue;
            int mod8 = p & 7;
            if (mod8 != 1 && mod8 != 7)
                continue;
            long inv2 = (p + 1L) / 2;
            long root;
            if (mod8 == 7) {
                long sqrt2 = modPow(2, (p + 1L) / 4, p);
                root = sqrt2 * inv2 % p;
            } else {
                root = tonelliShanks(inv2, p);
                if (root == 0)
                    continue;
            }
            int r1 = (int) root, r2 = r1 == 0 ? 0 : p - r1;
            long half = (p + 1L) / 2;
            int sr = (int) Math.sqrt(half);
            while ((long) (sr + 1) * (sr + 1) <= half)
                sr++;
            while ((long) sr * sr > half)
                sr--;
            int skipN = ((long) sr * sr == half) ? sr : -1;
            mark(composite, r1, p, limitN, skipN);
            if (r2 != r1)
                mark(composite, r2, p, limitN, skipN);
        }
        int count = 0;
        for (int n = 2; n <= limitN; n++)
            if (!composite[n])
                count++;
        System.out.println(count);
    }

    static void mark(boolean[] composite, int residue, int p, int limitN, int skipN) {
        int n = residue;
        if (n < 2)
            n += ((2 - n + p - 1) / p) * p;
        for (; n <= limitN; n += p)
            if (n != skipN)
                composite[n] = true;
    }

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

    static long tonelliShanks(long n, int p) {
        if (n == 0)
            return 0;
        if (p == 2)
            return n;
        if (modPow(n, (p - 1) / 2, p) != 1)
            return 0;
        if (p % 4 == 3)
            return modPow(n, (p + 1) / 4, p);
        long q = p - 1;
        int s = 0;
        while ((q & 1) == 0) {
            q >>= 1;
            s++;
        }
        long z = 2;
        while (modPow(z, (p - 1) / 2, p) != p - 1)
            z++;
        long m = s, c = modPow(z, q, p), t = modPow(n, q, p), r = modPow(n, (q + 1) / 2, p);
        while (t != 1) {
            long i = 1, t2 = t * t % p;
            while (t2 != 1) {
                t2 = t2 * t2 % p;
                i++;
            }
            long b = modPow(c, 1L << (m - i - 1), p);
            r = r * b % p;
            t = t * b % p * b % p;
            c = b * b % p;
            m = i;
        }
        return r;
    }
}