/* submitted by 510026284956-0001@t-online.de (Edgar Binder) 2003-09-10 */

#include <math.h>
#include <string.h>

//#define LastEntry 4095
#define LastEntry 8191

unsigned long long pi(unsigned long long x)
{

	unsigned long Cache[LastEntry + 2][4];
	long Dep, Next, N, i, Count;

	memset(Cache, 0, (LastEntry + 2) * 16);

	for (i=2, Count=0; i<=int(sqrt(x)); i++, ++Count)
	{
		Cache[i][0]=1;Cache[i][1]=i + i;
		for (long j=2; j<=int(sqrt(i));j++) { if (i % j == 0) {Cache[i][1]=0;Count--;break;}}
	}


	for (i=2, Dep=3; i<= (x + 1)>> 1; i++, Dep = (Dep + 2) & LastEntry)
	{
		N = Cache[Dep][0];
		if (N == 0) Count++; else
		for (long j = 1; j<=N; j++)             
		{
			Next = (Dep + Cache[Dep][j]) & LastEntry;
			Cache[Next][++Cache[Next][0]]=Cache[Dep][j];
		}

		Cache[Dep][0]=0;
	} 

	return ((x>=2) && (x<=3))?++Count:Count;
}