/*
  Name: PrimeFinder
  Author: Rik
  Description: Finds the nth prime using a modification of the sieve of eratosthenes
*/


#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <memory.h>


#define _DEBUG_




const unsigned int uiNumberOfPrimesToFind = 10001;



int main()
{

 time_t timeStart, timeEnd;

 #ifdef _DEBUG_
 unsigned int uiDivisions = 0;
 unsigned int uiIncrements = 0;
 #endif


 unsigned int uiPrimesFound = 0;

 unsigned int uiPrimeList[uiNumberOfPrimesToFind];
 memset(&uiPrimeList,0,(uiNumberOfPrimesToFind*sizeof(unsigned int)));




 time(&timeStart);

 /***********************************************************************************/
 /*   2 is the only even prime number. Code afterwards only checks for odd primes.  */
 /***********************************************************************************/

 uiPrimeList[uiPrimesFound] = 2;
 ++uiPrimesFound;


 /*********************************************************/
 /*   uiIncrement and uiMinimum should be even integers   */
 /*********************************************************/

 unsigned int uiRounds = 0;
 unsigned int uiIncrement = 367398; // Optimum number for finding the 31337th prime

 bool bFirstIncrement = true;


 while( uiPrimesFound < uiNumberOfPrimesToFind )
 {

     unsigned int uiMinimum = 2 + (uiRounds*uiIncrement);
     unsigned int uiMaximum = uiMinimum + uiIncrement;

     unsigned int uiListSize = ((uiMaximum - uiMinimum)>>1);

     #ifdef _DEBUG_
     //++uiDivisions;
     ++uiIncrements;
     #endif

     unsigned int uiTempNumberList[uiListSize];

     unsigned int uiNewOddNum = (uiMinimum+1);

     for( unsigned int uiIndex = 0; uiIndex < uiListSize; ++uiIndex,uiNewOddNum+=2 )  uiTempNumberList[uiIndex] =  uiNewOddNum;





     for( unsigned int uiIndex = 0; uiIndex < uiListSize; ++uiIndex )
     {
        unsigned int uiPrimeCandidate = uiTempNumberList[uiIndex];

        if( uiPrimeCandidate ) {

         bool bIsPrime = true;


         if( !bFirstIncrement )
         {
                 unsigned int uiPrime = 0;
                 unsigned int uiFractionOfCandidate = 0;
                 for( unsigned int uiPrimeListIndex = 0;  uiPrimeListIndex < uiPrimesFound; ++uiPrimeListIndex )
                   {
                       #ifdef _DEBUG_
                       uiDivisions+=2;
                       #endif


                      uiPrime = uiPrimeList[uiPrimeListIndex];

                      if( uiPrimeListIndex > 0 )
                      {
                         uiFractionOfCandidate = (uiPrimeCandidate/uiPrimeList[uiPrimeListIndex-1]);
                        if( uiPrime > (uiFractionOfCandidate) ) break;
                      }

                      if( ( uiPrimeCandidate % uiPrime )  == 0 )
                        {
                             bIsPrime = false;
                             break;
                        }
                   }
        }



        if( bIsPrime )
        {
            uiPrimeList[uiPrimesFound] = uiPrimeCandidate;
            ++uiPrimesFound;

            if( uiNumberOfPrimesToFind == uiPrimesFound ) break;

            unsigned int uiIndex2 = uiIndex;
            while( uiIndex2 < uiListSize ) {  uiTempNumberList[ uiIndex2 ] = 0; uiIndex2 += uiPrimeCandidate;  }
        }
    }

     }


     bFirstIncrement = false;
     ++uiRounds;

 }



  time(&timeEnd);

 printf("%u Prime: %u\n",uiNumberOfPrimesToFind,uiPrimeList[uiNumberOfPrimesToFind-1]);
 printf("Time taken: %.2lf\n\n",difftime(timeEnd,timeStart));

 #ifdef _DEBUG_
 printf("Divisions necessary: %u\n\n",uiDivisions);
 printf("Increments necessary: %u\n\n",uiIncrements);
 #endif

 system("pause");

}