#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#include <algorithm>
#include <vector>
#include <map>
using namespace std;

vector<unsigned long>leapfrog(unsigned long prime_start, unsigned long end, bool helper)
{
	map<unsigned long,unsigned long>v;
	vector<unsigned long>primes;
	vector<unsigned long>new_primes;
	double primorial;
	unsigned long count = 0;

	if (!helper)
	{
		primes = leapfrog(4,sqrt(prime_start),true);
		primes.insert(primes.begin(),3);
		primes.insert(primes.begin(),2);
	}
	else
	{
		primes.push_back(2);
		primes.push_back(3);
	}
	
	long i;
	for (i = 0; i < primes.size(); i++)
	{
		unsigned long prime = primes[i];
		//Definitely -1, because to start at 0 makes the first square a false prime
		v[prime] = ((prime_start/prime)-1)*prime;
	}

	//Must be global, because of 'stragglers' (the first being 133)
	map<unsigned long,bool>mini_table;
	unsigned long start = prime_start;
	while (start < end)
	{
		unsigned long lastprime = primes[primes.size()-1];
		v[lastprime] += lastprime;
		mini_table[v[lastprime]] = true;
		unsigned long last = 0;

		for (i = primes.size()-2; i >= 0; i--)
		{
			unsigned long prime = primes[i];
			while (v[prime] <= v[lastprime])
			{
				v[prime] += prime;
				mini_table[v[prime]] = true;
				last = v[prime];
			}
		}

		unsigned long last_prime = primes[primes.size()-1];
		long prime;
		for (prime = last_prime+1; prime < last_prime*2; prime++)
		{
			if (
				(prime*prime >= start) &&
				(prime*prime < last) &&
				//Finding gcd with the primorial is better than looking in the new primes table
				//But we're not using primorials because we're limited to numbers up to 4 billion
				(find(new_primes.begin(),new_primes.end(),prime) != new_primes.end())
                )
			{
				primes.push_back(prime);
//				primorial = primorial * prime;
				mini_table[prime*prime] = true;
				v[prime] = prime*prime;
			}
		}

		for (i = start; (i < last) && (i < end); i++)
		{
			if (!mini_table[i])
			{
				if (i >= prime_start)
				{
					new_primes.push_back(i);
					printf("%ld\t\t%ld\n",i,count++);
				}
			}
			else
			{
			   //Deletes it from memory
				mini_table.erase(mini_table.find(i));
			}
		}
		start = last+1;
	}
	return new_primes;
}

int main(int argc,char **argv)
{
	if (argc == 3)
	{
		leapfrog(atol(argv[1]),atol(argv[2]),false);
	}
}