////////////////////////////////////////////////////////////////////////////////
//                                                                            //
// PRIMES.CPP - Assignment #5                                                 //
// by flamingspinach                                                          //
//                                                                            //
// CS 161 "Computer Science I" (CRN #30496)                                   //
//                                                                            //
//    started | 2005-07-20 10:24:18                                           //
//   finished | 2005-07-20 13:19:09                                           //
//            |                                                               //
//     devenv | Bloodshed Dev-C++ 4.9.9.2                                     //
//    sources | [none]                                                        //
//                                                                            //
////////////////////////////////////////////////////////////////////////////////

#include <iostream>                              // For terminal ops
#include <iomanip>                               // For stream manipulators
#include <cstdlib>                               // For atol()
#include <vector>                                // For STL vector ops
using namespace std;

long RANGE = 50000;                              // Upper limit of testing range (lower assumed as 2)

void doEratosthenes(vector<long> &numbers) {
    long i, j;                                                      // Simple counter vars
    for (i = 2; i * i <= RANGE; i++)                                // pow() would probably be less efficient, and also it is not overloaded for (long, long). And of course a sqrt() call would be much too wasteful.
        for (j = 2 * i; j <= RANGE; j += i)
            numbers[j - 2] = 0;                                     // This is the Sieve of Eratosthenes. I use 0 because later I will cast to bool, to sort out the primes.
    
    return;
}

void doOutput(vector<long> &numbers) {
    long i;
    long numOfChiliads = static_cast<long>(RANGE / 1000.0);
    vector<long> chiliads(numOfChiliads);
    for (i = 0; i < numOfChiliads; i++)
        chiliads[i] = 0;                                            // Initializing the array - since it is variable-sized it cannot be done with = {0}.
    
    for (i = 0; i <= RANGE - 2; i++)
        if (numbers[i]) chiliads[(i + 2) / 1000] += 1;
    
    cout << endl << setw(15) << left << "Start" << setw(15) << left << "End" << setw(15) << left << "Number of Primes" << endl;
    for (i = 0; i < numOfChiliads; i++)
        cout << setw(15) << left << 1000 * i + 1 << setw(15) << left << 1000 * (i + 1) << setw(15) << left << chiliads[i] << endl;
    
    return;
}

int main (int argc, char** argv) {
    // Declarations
    long i;
    
    // Check arguments for a maximum number, input if none exists, round to nearest 1000
    if (argc == 2) RANGE = (atol(argv[1]) / 1000) * 1000;
    else {
        cout << "Search for primes up to what number? (to the nearest 1000): ";
        cin >> RANGE;
        RANGE /= 1000;
        RANGE *= 1000;
    }
    
    vector<long> numbers(RANGE - 1);                    // Bad style to declare late, but you can see why it is necessary
    
    for (i = 2; i <= RANGE; i++) numbers[i - 2] = i;    // Fill numbers[] with the integers from 2 to RANGE

    doEratosthenes(numbers);
    doOutput(numbers);
    
    // Lead-out (comment out these lines and supply RANGE by command line if time-testing)
    cin.ignore(65535, '\n').get();               // Allow user to read output
    return 0;                                    // Clean exit code
}