#include <iostream.h>
#include <time.h>
#include <stdlib.h>

unsigned S2(unsigned x, unsigned yin);

#define cache_size 65536

int f_cache[cache_size];

unsigned JSHpi1(unsigned xin) {

        // cache most common answers

        if (xin<cache_size) {
                if (f_cache[xin - 1] == -1)
                        f_cache[xin - 1] = xin - S2 (xin, xin) - 1;
                return f_cache[xin - 1];
        }
        return xin - S2 (xin, xin) - 1;
}

unsigned S2 (unsigned x, unsigned yin) {
        unsigned sum = 0, i, j=0, k=1, l, sum1, sum2, a1, a2, a3;
        const unsigned dx=1;

        for(unsigned i=2; i*i<=yin; i++) {
                a1 = JSHpi1 (i);
                a2 = JSHpi1 (i - dx);
                sum2 = a1 - a2;
                j += k;
                k += 2;
                if (sum2 != 0) {
                        int tmp2 = x / i;
                        if (j < tmp2)
                                a3 = tmp2 - S2 (tmp2, j) - 1;
                        else
                                a3 = JSHpi1 (tmp2);
                        sum1 = a3 - a2;
                        sum += sum1 * sum2;
                }
        }
        return sum;
}

unsigned long long pi(unsigned long long n)
{
        for (int i=0; i<cache_size; i++) f_cache[i] = -1;
	return JSHpi1(n);
}