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

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]);
        }

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

};

#include <iostream>
#include <stdio.h>

unsigned long long pi(unsigned long long n)
{
    unsigned long long sqrtn = sqrt(n+0.)+1;

    unsigned long long i,k,an,start = 1;

    bit a(n);

   for(i=4;i<n;i+=2)a.biton(i);

    while(start <= sqrtn)
    {
        start+=2;
        while(a.bitvalue(start) and start<=sqrtn)start+=2;
        for(i=start*start;i<n;i+=start)a.biton(i);
    }
                
    an = 1;
    for(k=3;k<n;k+=2)an+=!a.bitvalue(k);

    return an;
        
}