/* Submitted 2003-09-05 by Daniel A. Jimenez (djimenez@cs.utexas.edu) */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
                        
unsigned find (unsigned b, unsigned i, unsigned a, unsigned c)
{
	unsigned j, k, n;
	n = 6 * i + c;
	b *= 6;
	b += (n-(b%n));
	for (j=b; ; j+=n)
	{
		k = (j-a)/6;
		if (k * 6 + a == j) if (k != i) return k;
	}
}
                
unsigned long long pi (unsigned long long v)
{
	char A0[65536], A1[65536];
	unsigned b, s, r, i, j, k, l, w, f1, f2, n;
	char    *p0, *p1;

	n = 0;
	w = 1 + v/6;
	if (v >= 2) n++;
	if (v >= 3) n++;
	if (v >= 5) n++;
	if (v >= 7) n++;
	if (v >= 11) n++;
	for (b=0; b<=w; b+=65536)
	{
		r = b + 65536;
		if (r > w) r = w;
		l = 1 + (unsigned) sqrt (r);
		memset (A0, 1, r-b);
		memset (A1, 1, r-b);
		for (i=0; i<l; i++)
		{
			f1 = i * 6 + 1;
			f2 = i * 6 + 5;
			if (f1 != 1)
			{
				for (j=find(b,i,1,1); j<r; j+=f1) A0[j-b] = false;
				for (j=find(b,i,5,1); j<r; j+=f1) A1[j-b] = false;
			}
			for (j=find(b,i,5,5); j<r; j+=f2) A1[j-b] = false;
			for (j=find(b,i,1,5); j<r; j+=f2) A0[j-b] = false;
		}
		s = b;
		p0 = &A0[0];
		p1 = &A1[0];
		if (b == 0)
		{
			s = 2;
			p0 += 2;
			p1 += 2;
		}
		for (i=s; i<r; i++)
		{
			k = i * 6 + 1;
			if (k > v) break;
			n += *p0++;
			k = i * 6 + 5;
			if (k > v) break;
			n += *p1++;
		}
	}
	return n;
}