/* Written by: Herb Savage    */
/* Date:       15 Sep 2003    */
/* Purpose:    Computes pi(X) */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define TRUE  1
#define FALSE 0
   
int prime(unsigned x) {
   unsigned i,t;
   if (x < 2)
      return FALSE;
   if (x == 2)
      return TRUE;
   if (!(x & 1))
      return FALSE;
   i = 3;
   for (;;) {
      t = x / i;
    if (t < i) break;
      if (t * i == x)
         return FALSE;
      i += 2;
      }
   return TRUE;
   }

unsigned nextPrimeM(unsigned x) {
   if (x < 2)
      return 2;
   if (!(x & 1))
      x--;
   while (!prime(x += 2));
   return x;
   }

#define cache_size 10000
unsigned np_cache[cache_size];

unsigned nextPrime(unsigned x) {
   if (x < cache_size) {
      if (!np_cache[x])
         np_cache[x] = nextPrimeM(x);
      return np_cache[x];
      }
   return nextPrimeM(x);
   }

unsigned pi_n(unsigned end, unsigned maxP) {
   unsigned others,p,primes;
   others = end - 1;
   if (others < 1)
      return 0;
   p = 0;
   primes = 0;
   for (;;) {
      p = nextPrime(p);
    if ((p * p > end) || (p >= maxP)) break;
      if (p == 2)
        others -= (others + 1) / 2;
      else if (p == 3)
        others -= (others + 2) / 3;
      else
        others -= pi_n(end/p,p) - (primes - 1);
      primes++;
      }
   return primes + others;
   }
   
unsigned long long pi(unsigned long long v) {
   return pi_n(v,v);
   }