#include <math.h>
#include <vector>
#include <iostream>
#include <driver.h>

std::vector<unsigned> primeArray;

// Routine to compute the ix'th prime.

static unsigned prime(unsigned ix)
{
  while(ix >= primeArray.size())
  {
    // glory be, we've run out of primes!
    unsigned last = primeArray[primeArray.size()-1];
    bool foundPrime = false;

    while(!foundPrime)
    {
      if(last % 6 == 1) last += 4;
      else last += 2;

      // don't bother testing 2 and 3

      for(unsigned j = 3; j < primeArray.size(); j++)
      {
        if(primeArray[j] * primeArray[j] > last)
        {
          // we've run the gauntlet and know 'last' is prime
          primeArray.push_back(last);
          foundPrime = true;
          break;
        }
        if(last % primeArray[j] == 0)
        {
          break; // not prime, sorry
        }
      }
    }
  }

  return primeArray[ix];
}

// Routine to compute the number of primes less than or equal to lim
// This routine has a number of latent bugs which are not elicited
// by the rest of the implementation; a more general routine would
// use a binary search if the last prime is greater than the limit.

static unsigned stupidpi(unsigned lim)
{
  while(primeArray[primeArray.size()-1] < lim)
    prime(primeArray.size());

  return primeArray.size() - 2;
}

// Legendre's function.

static double phi(double x, unsigned n)
{
  if(x < 1) return 0;
  if(x < 2) return 1;
  if(n == 0) return floor(x);

  // Since the primes are strictly monotonic, if we know
  // the next iteration is going to be phi(y,something) where
  // y < 1, don't bother explicitly computing prime(n).

  if(n > primeArray.size() && primeArray[primeArray.size() - 1] > x)
    return phi(x, n-1);

  return phi(x, n-1) - phi(x / prime(n), n-1);
}

unsigned long long pi(unsigned long long x)
{
	if(x < 2) return 0;
	if(x < 3) return 1;
	if(x < 5) return 2;
	if(x < 7) return 3;

	if(primeArray.size() == 0)
	{
		primeArray.push_back(1); // p_0 is not defined so it doesn't matter
		primeArray.push_back(2);
		primeArray.push_back(3);
		primeArray.push_back(5);
	}

	unsigned long long a = pi((unsigned long long) floor(sqrt(x)));
	return phi(x, a) - 1 + a;
}