-1

I'm tasked with creating a vector of 'x' numbers and finding the prime numbers in that vector using the "Sieve of Eratosthenes." I iterated through the vector to replace all of the non-prime elements with zero. Then I made a for loop to erase all of the zeros. The loop erased most of the zeros however it skipped some 

vector<int> primes;
int userNum = 0; //variable for user to input the size of the vector
cout << "Enter your num, brah";
cin >> userNum;
for (int i = 2; i < userNum; i++) //creates a vector of numbers
{
    primes.push_back(i);
}


int j = 0; //variable to find non-primes

for (int p = primes[0]; p < primes.size(); p++) //loop to replace non-primes with zeros
{
    j = p+p;

    while (j < (primes.size() +2)) {



        replace(primes.begin(), primes.end(), j, 0);

        j+= p;

    }
}

for (int y = 0; y < primes.size(); y++) { //loop to erase the zeros from the vector
    cout << "y1 " << primes[y] << " ";   //cout simply just to find see what is going on
    if (primes[y] == 0) {
        primes.erase(primes.begin() +y);
        cout << "y2: " << y << endl;  //cout simply just to find see what is going on
    }

}

cout << "New Vector is: " << endl; //loop to print the vector
for (int l = 0; l < primes.size(); l++)
{

    cout << primes[l] << ", ";
}

The output I get is: New Vector is: 2, 3, 5, 7, 0, 11, 13, 0, 17, 19, 0, 23, 0, 0, 29, 31, 0, 0, 37, 0, 41, 43, 0, 47, 0, 0, 53, 0, 0, 59, 61, 0, 0, 67, 0, 71, 73, 0, 0, 79, 0, 83, 0, 0, 89, 0, 0, 0, 97, 0, Program ended with exit code: 0

caffeinatedkomodo
  • 1
  • 1
  • 1
  • Please post compilable code. –  Sep 14 '18 at 00:05
  • 1
    Unrelated: A common solution for this is a `vector` of booleans (though possibly not `vector` because [it is something of a odd duck](https://en.cppreference.com/w/cpp/container/vector_bool)) . Rather than removing elements from the `vector`, you initialize to true and set to the indexed value false when you've proved that a particular index cannot be prime. When done, you print out the indexes that are still true. This requires significantly less effort than removing most of the `vector`s elements one by one. – user4581301 Sep 14 '18 at 00:05
  • 2
    `primes.erase(std::remove(primes.begin(), primes.end(),0),primes.end());` -- Is this what you're trying to achieve? That line removes all the zeros. Now whether your prime number finder actually works, that's a different story. – PaulMcKenzie Sep 14 '18 at 00:06
  • You should learn about usage of iterators. You would get better readable and as bonus, even more efficient code with... – Aconcagua Sep 14 '18 at 01:10
  • The `+2` in the while loop useless - if `j` gets equal to size or size + 1, then we are out of vector bounds anyway and we just do work without effect as by your design, j cannot be within the vector any more... – Aconcagua Sep 14 '18 at 01:35
  • You are needlessly replacing 0 again and again with 0 for all those p that have been discovered by an earlier loop run. You can avoid this by checking `if(p != 0)` initially in the loop. – Aconcagua Sep 14 '18 at 01:38
  • `replace(primes.begin(), primes.end(), j, 0);` will iterate over the whole vector (hidden third nested loop). Provided you have the 0-check (see previous comment) applied already, you can simply do: `primes[j] = 0;` (without the check, you would replace very first prime as well...). – Aconcagua Sep 14 '18 at 01:41
  • You need to re-read the "Sieve of Eratosthenes". There is no erasing in that algorithm. From Wikipedia, "[S of E] does so by iteratively marking as composite the multiples of each prime, starting with the first prime number, 2." The sieve is processed (prime by prime) to mark each number as either prime or composite. An existing composite number is used to mark all numbers that are composed by that smaller prime. Thus, the prime numbers are used in the algorithm, and can not be erased. No erasing. – 2785528 Sep 14 '18 at 02:40

3 Answers3

4

There is no need to write a loop to remove an element from a vector. Use the erase-remove idiom

primes.erase(std::remove(primes.begin(), primes.end(), 0), primes.end());

The above uses std::remove to move the elements that are not to be erased to the "left side" or front of the vector, and returns the iterator that points to the first element that is to be removed "on the right side". Then primes.erase() actually removes the elements to erase from the vector by starting from the iterator returned from the call to std::remove.

You could break up the statement into two lines if you aren't sure how it works:

// returns an iterator to where the elements to erase are to be removed
auto iter = std::remove(primes.begin(), primes.end(), 0);

// Now actually erase them, starting at iter
primes.erase(iter, primes.end());
PaulMcKenzie
  • 34,698
  • 4
  • 24
  • 45
1

one problem for sure is that you're going to skip elements because when you delete something from a sequence the index of everything after it goes down by 1.

I've made a simplified version of your delete code here that just tries to delete every element from a vector:

string vecToStr(const vector<int> &foos) {
  std::stringstream result;
  std::copy(foos.begin(), foos.end(), std::ostream_iterator<int>(result, " "));
  return result.str();
}

int main() {
  vector<int> foos = { 0,1,2,3,4,5,6 };
  for (int y = 0; y < foos.size(); y++) { //loop to erase the zeros from the vector
    foos.erase(foos.begin() + y);
    cout << "foos is now: " << vecToStr(foos) << " y is " << y << "\n";
  }
  cout << "foos is now: " << vecToStr(foos) << "\n";
  char c;
  cin >> c;
}

Here is the output:

foos is now: 1 2 3 4 5 6  y is 0
foos is now: 1 3 4 5 6  y is 1
foos is now: 1 3 5 6  y is 2
foos is now: 1 3 5  y is 3
foos is now: 1 3 5

You can see how the 0th element is deleted, then the element with value 1 moves into index 0, but y then becomes 1, so it gets skipped, then 2 is deleted at index 1, and 3 moves into index 2, etc.

There are a variety of approaches to this (see Remove elements of a vector inside the loop) the old-fashioned C way of doing this is to go from the end:

  int y = foos.size();
  while(y--) {
    foos.erase(foos.begin() + y);
    cout << "foos is now: " << vecToStr(foos) << " y is " << y << "\n";
  }
aaron
  • 1,746
  • 1
  • 13
  • 24
  • Removing from the end won't yield invalid result, but using `erase` will repeatedly move all subsequent elements one position towards front, which is almost as inefficient as you can get... Better: have an iterator pointing to `foos.begin()` before the loop and move those elements that shall remain to: `*pos++ = vector[y]` (this is what `std::remove` actually does as well). Afterwards, remove all surplus elements in one single go: `foos.erase(pos, foos.end());`. – Aconcagua Sep 14 '18 at 01:54
  • @Aconcagua `foos.erase(foos.begin() + y);` deletes from the end, so no moving is required. e.g. in the example above you'd have: `1 2 3 4 5 6` then `1 2 3 4 5` then `1 2 3 4` ... – aaron May 29 '19 at 20:05
  • This all applies only for your specific scenario, as you are removing *all* elements *unconditionally* (but then you can just do `erase(begin + y, end)` without loop at all). Try the sample sequence in question (prime numbers with zeros contained) and remove only the latter ones conditionally. The remaining elements (the primes) will be moved repeatedly, no matter if you erase from beginning or end... – Aconcagua May 30 '19 at 13:01
0

The other answers make good suggestions -- erase remove idiom is well-known and useful.

However, the fix for your code is simple. Look at this loop

for (int y = 0; y < primes.size(); y++) { //loop to erase the zeros from the vector
    if (primes[y] == 0) {
        primes.erase(primes.begin() +y);
    }
}

It can be fixed just by not incrementing y when an element is removed.

for (int y = 0; y < primes.size(); /* no increment here */) { //loop to erase the zeros from the vector
    if (primes[y] == 0) {
        primes.erase(primes.begin() +y);
    } else {
      y++;
    }
}
wrhall
  • 1,288
  • 1
  • 12
  • 26
  • 1
    While correct algorithm, it is inefficient as you repeatedly move subsequent elements towards front (resulting in O(n^2), whereas O(n) can easily be achieved by a different [algorithm](https://stackoverflow.com/a/52324178/1312382)). – Aconcagua Sep 14 '18 at 02:40
  • Agreed - erase remove does this in a single efficient pass. But I wanted to show the op the minimal modification needed to make their code correct. – wrhall Sep 14 '18 at 02:41
  • OK, that's a point as well. As using `erase` within the while loop, efficiency is already gone anyway... – Aconcagua Sep 14 '18 at 03:03