#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

class Primes
{
  public:
  static Primes *getInstance()
  {
    if( !instance )
      instance = new Primes();
    return instance;
  }
  unsigned int operator[](size_t);
  size_t index(unsigned int);
  size_t closestIndex(unsigned int);
  
  private:
  static Primes *instance;
  Primes()
  {
    unsigned int table[] = { 2, 3, 5 };
    primes.insert( primes.begin(), table, table + sizeof( table ) / sizeof( table[ 0 ] ) );
  }
  vector<unsigned int> primes;
};

Primes *Primes::instance = 0;

unsigned int Primes::operator[]( size_t n )
{
  if( primes.size() <= n )
  {
    unsigned int last = primes[ primes.size() - 1 ];
                  
    while( primes.size() <= n )
    {
      last++;
      unsigned int sqlast = sqrt( last ) + 1;
      bool isPrime = true;
      for( int i = 0; isPrime && ( primes[ i ] <= sqlast ); ++i )
        isPrime = ( ( last % primes[ i ] ) != 0 );
      if( isPrime )
        primes.push_back( last );
    }
  } 
  return primes[ n ];
}

size_t Primes::index(unsigned int p)
{
  size_t search = closestIndex( p );
  return ( (*this)[ search ] == p ) ? search : -1;
}

size_t Primes::closestIndex(unsigned int p)
{
  if( p <= 2 )
    return 0;
  size_t last = primes.size() - 1;

  bool wasSearch = false;

  while( (*this)[ last++ ] < p )
    wasSearch = true;

  last = primes.size() - 1;
  if( primes[ last ] == p )
    return last;
  if( wasSearch )
    return last - 1;

  size_t step = last + 2;
  while( step > 0 )
  {
    step /= 2;
    if( primes[ last ] == p )
      return last;
    if( primes[ last ] > p )
      last -= step;
    else
      last += step;
  }
  return last;
}

int main()

{
  Primes &primes = (*Primes::getInstance());
  for( int i = 0; i < 10000; ++i )
    cout << primes[ i ] << " ";
}