////////////////////////////////////////////////////////////////////////////////// //// 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 opsusing 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}