//Recommmended Compiler - DEV C++ Dont Try Turbo C++ your system may crash

//Also use extension .cpp than c to access cout instead of printf
             

#define CAP 500000 //Set This value according to yourself you may hurt your computer
#define ARRAYSTORAGE 160000 

// Change Caps Value To Increase Search Limit.
// Change ArrayStorage To Increase Array Size, can be limited by compiler especially older ones.

#include <stdio.h>
#include <conio.h>
#include <process.h>
#include <stdlib.h>
#include <iostream.h>

unsigned long long int counter;//Keep Count of number of items in storage
unsigned long long int liststorage [ARRAYSTORAGE];  //Can store upto ARRAYSTORAGE MACRO VALUE Prime Numbers

void primelist ()
 {
   printf ("Generating Prime List, Time taken depends upons CAP VALUE, Please wait ....");
   unsigned long long int i,j;
   for (i = 3; i < CAP; i++)   // Loops from 3 to UPPERLIMIT
    {
      for (j = 0; j < counter; j++)
         {
          if (!(i%liststorage[j])) break; // Number is Prime
          if (j == counter-1) //Number is Not Prime
           {
             liststorage [counter] = i;//Add Item To List
             counter++;//Increment Item Counter
             if (counter > ARRAYSTORAGE)
              {
                printf ("\n\nArray Overrun .... Please Allocate more memmory to Array");
                getch ();
                exit (0);
               }
              break;
           }
        }    
    }
 
 printf ("\n\nNumber of Primes In List : %d " ,counter);
 
 }

int bsearch (int num) //Binary search function returns 1 if num exist and 0 otherwise
 {
   unsigned long long int mid,lower,upper;
   lower = 0;
   upper = counter;
   for ( mid = (lower+upper)/2; lower <= upper; mid = (lower + upper)/2)
      {
         if ( liststorage [mid] == num)
           {
             return 1;
           }
         if (liststorage [mid] > num)
           upper = mid - 1;
         else
           lower = mid +1;
       }
    return 0;
 }

unsigned long long int power (int input) // ouputs a power of 2;
 {
   unsigned long long int ouput = 1;
   int i;
   for (i = 0; i<input;i++)
     {
       ouput *= 2;
     }

   if (ouput <= 0)
     {
       printf ("\n\nUnsigned long long int range overrun ... this is the largest value in C, beyond this c is helpless");
       getch ();
       exit (0);
     }
   return ouput;

}

void perfectlist ()
 {
   printf ("\n\nPerfect Number List : ");
   unsigned long long int i;
   for (i = 0;i < counter; i++)
      {
        unsigned long long int check1 = power (liststorage [i]);
        if (check1 > CAP)
            {
              printf ("\n\nSeach Limit Overrun ....Increase search limit");
              getch ();
              exit (0);
            }
        if (bsearch (check1 -1)) //That is 2^n - 1 is a prime
           {
              cout << (check1/2)* (check1 - 1)<<endl;
           }
        }
  }
             

int main ()

{
  counter = 1;  // Intialize Counter
  liststorage [0] = 2; // Put 2 in the List
  //clrscr (); //uncomment if using turbo C/C++
  primelist ();
  perfectlist ();
  getch ();
  return 0;
}