#include 

#include 

#include 

#define MAX_INT (unsigned long)(pow(2, 25))

#define MY_DEBUG 0

int main()

    {

     clock_t start_clock, end_clock;

     unsigned long i, j, k, odd_greater_than_1, n, up_bound = MAX_INT;

     unsigned char *prime_map;

     start_clock = clock();

     odd_greater_than_1 = (up_bound - 1) / 2;

     prime_map = new unsigned char[odd_greater_than_1];

     for (i = 0; i < odd_greater_than_1; i++)

     prime_map[i] = 1;

     n = unsigned long((sqrt(up_bound) - 3) / 2.0);

     for (i = 0; i <= n; i++)

         {

         if (prime_map[i] == 1)

             {

             k = 2 * i + 3; // new prime

             for (j = 2 * i * (i + 3) + 3; j < odd_greater_than_1; j = j + k)

                 {

                 prime_map[j] = 0;

                 }

                 }

                 }

                 end_clock = clock();

                 if (MY_DEBUG)

                     {

                     cout << setw(10) << 2;

                     for (j = 0; j < odd_greater_than_1; j++)

                         {

                         if (prime_map[j] == 1)

                             {

                             cout << setw(20) << 2 * j + 3;

                             }

                             }

                             cout << endl;

                             }

                             delete [] prime_map;

                             cout << "Total time to get list: " << end_clock - start_clock << " ms" << endl;

                             return 0;

                        }