#include <stdio.h>
#include <tchar.h>
#include <memory.h>

// Created by: Hani Atassi (10.06.05)

#define MAX_PRIME 100
int g_primes[MAX_PRIME + 1] = {0};

// Initializes the prime array with the following
//   -1	   The number is not prime
//    n    where n (1, 2, ...) the order of the prime number
void InitializePrimesArray()
{
	int lastPrimeOrder = 0;
	int i;
	if (MAX_PRIME >= 0) g_primes[0] = -1;	// 0 is not prime
	if (MAX_PRIME >= 1) g_primes[1] = -1;	// 1 is not prime
	// Investigate all other numbers
	for (i = 2; i <= MAX_PRIME / 2; i++)
	{
		// if the number is already set ignore it
		if (g_primes[i] != 0)
			continue;
		// set the current number as prime, and set the order
		g_primes[i] = ++lastPrimeOrder;
		// all the numbers afterword that are multible of this number are not prime
		for (int j = i * 2; j <= MAX_PRIME; j += i)
			g_primes[j] = -1;
	}
	// Fill the rest of the orders 
	for (; i <= MAX_PRIME; i++)
	{
		if (g_primes[i] == 0)	// if the number is prime
			g_primes[i] = ++lastPrimeOrder;
	}
}

// Returns the order of the given number or -1 if the number is not prime
int FindOrderOfPrime(int number)
{
	if (number < 0 || number > MAX_PRIME)
		return -1;	// or throw an exception
	return g_primes[number];
}

// Returns the prime number at the given order
int FindPrimeOfOrder(int order)
{
	// you could implement Binary search here to make this much faster
	// but just for the hack of this brain quiz, i am doing it in O(N)
	for (int i = 2; i <= MAX_PRIME; i++) 
	{
		if (g_primes[i] == order)
			return i;
	}
	return -1;	// couldn't found, the order is out of scope
}

int _tmain(int argc, _TCHAR* argv[])
{
	InitializePrimesArray();

	printf("Order of 1 = %d\n", FindOrderOfPrime(1));
	printf("Order of 2 = %d\n", FindOrderOfPrime(2));
	printf("Order of 3 = %d\n", FindOrderOfPrime(3));
	printf("Order of 100 = %d\n", FindOrderOfPrime(100));
	printf("Order of 7 = %d\n", FindOrderOfPrime(7));
	printf("Order of 43 = %d\n", FindOrderOfPrime(43));
	printf("Order of 50 = %d\n", FindOrderOfPrime(50));
	printf("Order of 53 = %d\n", FindOrderOfPrime(53));

	printf("\n");

	printf("Prime at order 1 = %d\n", FindPrimeOfOrder(1));
	printf("Prime at order 2 = %d\n", FindPrimeOfOrder(2));
	printf("Prime at order 10 = %d\n", FindPrimeOfOrder(10));
	printf("Prime at order 20 = %d\n", FindPrimeOfOrder(20));

	return 0;
}