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

std::vector<unsigned> primeArray;

unsigned prime(unsigned ix)
{
	while(ix >= primeArray.size())
	{
		// glory be, we've run out of primes!
		unsigned last = primeArray[ix-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)
				{
					primeArray.push_back(last);
					foundPrime = true;
					break;
				}
				if(last % primeArray[j] == 0)
				{
					break; // not prime, sorry
				}
			}
		}
	}

	return primeArray[ix];
}

unsigned long long pi(unsigned long long x)
{
	primeArray.push_back(1); // pi_0 is undefined
	primeArray.push_back(2);
	primeArray.push_back(3);
	primeArray.push_back(5);
	primeArray.push_back(7);

	while(primeArray[primeArray.size()-1] < x)
		prime(primeArray.size());

	return primeArray.size() - 2;
}