/* submitted by jrodgers@aug.edu 2003-09-10 */

#include <math.h>

class bit
{
        
        char *bitarray;
        char list[8];

        public:
                
        bit(unsigned long long length)
        {
                length=(length+1)/8;
                bitarray=new char[length];
                for(unsigned long long i=0;i<length;i++)bitarray[i]=0;
                list[0]=1;
                list[1]=2;
                list[2]=4;
                list[3]=8;
                list[4]=16;
                list[5]=32;
                list[6]=64;
                list[7]=128;               
  
        }
        
        ~bit(){delete bitarray;}        
        
        void biton(unsigned long long pos)
        {
                unsigned long long rec = pos/8;
                bitarray[rec]=(bitarray[rec] | list[pos%8]);
        }

        void bitflip(unsigned long long pos)
        {
                unsigned long long rec = pos/8;
                bitarray[rec]=(bitarray[rec] ^ list[pos%8]);
        }

        bool bitvalue(unsigned long long pos)
        {
                unsigned long long rec = pos/8;
                return (bitarray[rec] & list[pos%8]);
        }
        
};

unsigned long long pi(unsigned long long n)
{
	unsigned long long sqrtn = sqrt(n+0.);
	unsigned long long m;
	unsigned long long i;
	unsigned long long k;

	int j;
	unsigned long long start = 1;

	bit a(n);

	while(start < sqrtn)
	{
		start++;
		while(a.bitvalue(start)!=0 and start<=n)start++;     // The Prime machine
		for(i=start*start;i<n;i+=start)a.biton(i);
	}

	int pi = 1;
	for(k=3;k<n;k+=2)pi+=(!a.bitvalue(k));

	return pi;
}