#include <iostream>
#include <vector>

static bool NOTPRIME = false, PRIME = true;

void boolsieve(std::vector<bool> & b, unsigned n)
{
	b.reserve(n);

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

	b[0] = NOTPRIME;
	b[1] = NOTPRIME;

	for(unsigned i=2;i*i<=n;i++)
	{
		if(b[i] == PRIME)
		{
			b[i] = PRIME;
			for(unsigned j=i*i;j<n;j+=i)
			{
				b[j] = NOTPRIME;
			}
		}
	}
}

unsigned long long pi(unsigned long long x)
{
	std::vector<bool> vec;

	boolsieve(vec, x);
	unsigned long long cnt = 0;
	for(unsigned i = 0; i < x; i++)
		if(vec[i] == PRIME) cnt++;

	return cnt;
}