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

// #include "stdafx.h"  (windowsism -- ed.)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
// #include <windows.h>  (another windowsism -- ed.)

#define Number unsigned long long
#define PrimeTableSize 8192
#define NSize 8192
#define PSize 16
#define Empty 0xFFFFFFFF


Number Value = 4000000000;
Number Primes[PrimeTableSize];
Number Cache[NSize][PSize];

Number Kick(Number n, Number p, Number Max)
{

        Number i, p2, NewN, Res;

        NewN = n / p; Res = NewN;

        for (i = 1; i<Max; i++)
        {       
                p2 = Primes[i];
                if (p2 * p2 > NewN) {Res-=Max - i; break;}
                if ((NewN<NSize) && (i<PSize) && (Cache[NewN][i]!=Empty)) Res-=Cache[NewN][i]; else Res-=Kick(NewN, p2, i);
        };

        if ((n<NSize) && (Max<PSize)) Cache[n][Max]=Res;
        return Res;
}


Number pi(Number x)
{
        Number i, j, Halt, Res;
        Halt = 1; 

        for (i=0; i<NSize; i++) for (j=0; j<PSize; j++) Cache[i][j]=Empty;

        Primes[1]=2; i=3;
        do{
                Primes[++Halt] = i;
                for (j=1; Primes[j] * Primes[j]<=i; j++) if (i%Primes[j]==0) {Halt--; break;}
                i++;

        }while (Primes[Halt] * Primes[Halt] <= x);

        Res = x + (--Halt) - 1;

        for (i = 1; i<=Halt; i++) Res-=Kick(x, Primes[i], i);

        return Res;

}