#include <iostream>
#include <vector>

static bool NOTPRIME = false, PRIME = true;

void sieve(std::vector<bool> & b, std::vector<bool> & b2, unsigned n)
{
	b.reserve(n); // -1,5,11,17, etc.
	b2.reserve(n); // 1,7,13,19, etc.

	b[0] = NOTPRIME;
	b[1] = NOTPRIME;
	for(unsigned i=1;i<n;i++) b[i] = b2[i] = PRIME;

	unsigned long long t = 5, t2 = 7;

	// don't even bother with b[0] and b2[0]

	for(unsigned long long i=1;6*i*i-2*i<n;i++)
	{
		if(b[i] == PRIME)
		{
			// t = 6i-1; therefore t^2 = 36i^2-12i+1.
			// Also, t(t+2) = (6i-1)(6i+1)=36i^2-1.
			// t(t+1) is obviously not prime so we need
			// not worry about it.  Note that we still
			// increment by t.
			for(unsigned long long j=6*i*i;j<n;j+=t)
			{
				b[j] = NOTPRIME;
			}
			for(unsigned long long j=6*i*i-2*i;j<n;j+=t)
			{
				b2[j] = NOTPRIME;
			}
		}

		if(b2[i] == PRIME)
		{
			// t2 = 6i+1; therefore t2^2 = 36i^2+12i+1.
			// t2(t2+2) is a multiple of 3.
			// t2(t2+4)=(6i+1)(6i+5)=36i^2+36i+5.

			for(unsigned long long j=6*i*i+6*i+1;j<n;j+=t2)
			{
				b[j] = NOTPRIME;
			}
			for(unsigned long long j=6*i*i+2*i;j<n;j+=t2)
			{
				b2[j] = NOTPRIME;
			}
		}

		t += 6;
		t2 += 6;
	}
}

unsigned long long pi(unsigned long long n)
{
	// dumb pretests

	if(n < 2) return 0;
	if(n < 3) return 1;
	if(n < 5) return 2;

	unsigned l = (n+7) / 6;
	unsigned l2 = (n+5) / 6;

	std::vector<bool> vec, vec2;
	sieve(vec, vec2, l);

	unsigned long long knt = 2;

	for(unsigned long long i=1;i<l;i++)
		if(vec[i]) knt++;
	for(unsigned long long i=1;i<l2;i++)
		if(vec2[i]) knt++;

	return knt;
}