Write a function Eratos that takes an int indicating the upper range of the numb

Question

Write a function Eratos that takes an int indicating the upper range of
the numbers and a vector of ints that will contain the prime numbers:

    void Eratos( int length, vector< int > & );

The algorithm indicates that the first number, 2, is a prime and every
multiple of if cannot be a prime, so "cross them out: 4, 6, 8, etc."
When the algorithm indicates one should "cross out" a number, that is another
way to say "remove that number from the list." To remove a value at index
n, in a vector called v, we use the vector function erase( ):

    v.erase( v.begin( ) + n );

begin( ) is a vector function that returns an iterator;
we will discuss iterators later; for now you only need to know that
begin( ) returns the address of the beginning of the vector and n is an
index indicating that the element to be erased is at address

    v.begin( ) + n

in the vector. The function erase( ) physically removes that element from
the vector.

Write a second function operator << that will write the prime numbers.
It should display 10 numbers per line and use 5 positions for each number;
if the user asked for an upper bound of 100, your program should display

primes between 2 and 100:
    2    3    5    7   11   13   17   19   23   29
   31   37   41   43   47   53   59   61   67   71
   73   79   83   89   97

Your program should make sure that upper bound when searching for the
prime numbers is >= 2 and <= 300; otherwise your program should display
a message that upper bound is out of range and terminate the execution.

Explanation / Answer

#include <iostream>
#include <iomanip>        // For setw()
#include <vector>

using namespace std;

void Eratos(int, vector<int> &);
void showPrimeNumbers(vector<int> &);

int main() {
    vector<int> primeNumbersLessThan100;

    int len;
    cout << " Enter upper bound: ";
    cin >> len;

    Eratos(len, primeNumbersLessThan100);
    showPrimeNumbers(primeNumbersLessThan100);

    return 0;
}

void Eratos(int len, vector<int> &primeNumbers) {
    // Upper Bound Error Condition
    if (len > 300) {
        cout << "Upper bound is out of range" << endl;
        exit(0);
    }

    // Fill up the vector with numbers from 2 to len-1
    primeNumbers.empty();    // just in case the vector is not empty
    for (int i = 2; i < len; i++) primeNumbers.push_back(i);

    const int MARKED = -999;    // An identifier for striking out elements

    // Begin the sieve algorithm - strike off elements
    for (vector<int>::iterator i = primeNumbers.begin(); i != primeNumbers.end(); i++) {
        if (*i == MARKED) continue;    // skip previously marked elements

        int p = *i;

        // Mark every pth element starting from i for removal (striking out)
        for (vector<int>::iterator j = i + p; j < primeNumbers.end(); j += p) {
            *j = MARKED;
        }
    }   

    // Remove the marked elements
    for (vector<int>::iterator i = primeNumbers.begin(); i != primeNumbers.end(); ) {
        if (*i == MARKED) i = primeNumbers.erase(i);
        else i++;
    }
}

void showPrimeNumbers(vector<int> &primeNumbers) {
    cout << endl;
    for (int i = 0; i < primeNumbers.size(); i++) {
        cout << setw(5) << primeNumbers[i];
        // New line on every 10th element
        if ((i + 1) % 10 == 0) cout << " ";
    }
    cout << endl;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.