# Deleting Vector objects in a for loop

• 07-23-2009
Swordsman
Deleting Vector objects in a for loop
Hi all,

I am currently trying to implement a Sieve of Eratostheneses in C++ as part of a book I am learning. The objective is to find all of the prime numbers between 1 and n in a list. To achieve this, I am using two vectors, one that stores the numbers to check, and another to hold the actual numbers.

Here is the code for where I am up to:

Code:

```#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(int argc, char** argv[]) {         vector<int> nums;         vector<int> primes;         int n, numToCheck;         cout << "Please enter n: ";         cin >> n;         //populate num list         for(int i = 2; i < n; i++)         {                 nums.push_back(i);                 primes.push_back(i);         }         //move through array, eliminating multiples         for(int i = 0; i < nums.size(); i++)         {                 //assign number to check multiples of                 numToCheck = nums[i];                                 //cycle through vector and delete multiples                 for(int j = 0; j < primes.size(); j++)                 {                         if(primes[j] != numToCheck && primes[j]%numToCheck == 0)                         {                                 primes[j] = 0; //Number isn't prime                         }                 }         }         for(int i = 0; i < primes.size(); i++)         {                 cout << primes[i] << endl;         }         return 0; }```
The problem I currently have, is that I want to delete the number from the vector instead of just zeroing it. I have tried to use erase(primes.begin() + j) though this will produce an out of range error.

Can somebody point me in the correct direction please?
• 07-23-2009
anon
Code:

```                //cycle through vector and delete multiples                 for(int j = 0; j < primes.size(); j++)                 {                         if(primes[j] != numToCheck && primes[j]%numToCheck == 0)                         {                                 primes[j] = 0; //Number isn't prime                         }                 }```
This is very inefficient. To the point that this is not the sieve anymore. The idea is that you loop over only the multiples (and not all values).

Next I don't see what you need the vector with numbers in the first place, as it contains the same values as the primes list.

Then the idea of the sieve is that you mark things as non-prime while you are sieving. If you actually removed anything at this point, it would make it impossible to loop over the multiples (properly, not like you are doing). Not to mention that it would be terribly inefficient.

If you want to remove non-primes at the end of it all it would look something like:

Code:

```#include <algorithm> ... vec.erase(std::remove(vec.begin(), vec.end(), 0), vec.end());```
• 07-23-2009
Swordsman

I was using two vectors as the plan was to remove them as I go, and not just mark them, which looking at the algorithm, is the wrong way to do it. I started with the correct algorithm in my head, but in a quest to get it working, it seems to have changed a bit :)

Instead of looping over the multiples, I seem to be looping over every number and checking it as a multiple as you suggested. I have changed the code to this:

Code:

```//populate num list         for(int i = 2; i < n; i++)         {                 primes.push_back(i);         }         //move through array, eliminating multiples         for(int i = 0; i < primes.size(); i++)         {                 numToCheck = primes[i];                 //dont check already marked                 if(numToCheck > 0)                 {                         //removes multiples                         for(int j = numToCheck; j < primes.size(); j++)                         {                                 if((primes[j] % primes[i]) == 0)                                 {                                         primes[j] = 0;                                 }                         }                 }         }         primes.erase(std::remove(primes.begin(), primes.end(), 0), primes.end());         for(int i = 0; i < primes.size(); i++)         {                 cout << primes[i] << endl;         }```
This still seems inefficient though, can anybody suggest any optimisation ideas please?
• 07-23-2009
anon
Hint: modulus shouldn't appear anywhere in the code. You need to iterate over multiples: 2 is a prime => 4, 6, 8, 10 ... aren't, 3 is a prime => 6, 9, 12, 15... aren't etc.

Given the number is 2, what should the loop look like, so the loop counter has values 4, 6, 8...?
• 07-23-2009
Swordsman

My second for loop has changed to:

Code:

`for(int j = numToCheck; j < primes.size(); j += numToCheck)`
though I am still wondering how to mark the numbers in the correct position.

For example, the vector is populated, starting at 2 up until 10.
2, 3, 4, 5, 6, 7, 8, 9, 10

So presuming we are doing the run for multiples of three, primes[6] is actually equal to 8, hence I can't use primes[j].

How can I change a value inside of a vector, irrespective of it's position?
• 07-23-2009
anon
I guess you could put 0 and 1 in there as well? Typically I think you wouldn't store the numbers but zero for not prime and 1 for prime. So if you want to see whether 231 is prime you check whether primes[231] is 1 or 0.
• 07-23-2009
Swordsman
I've changed the initial array to include 0 and 1 to match the positions of the vector up.

Thanks for the help anon, here is the finished code:

Code:

```vector<int> primes;         int n, numToCheck;         cout << "Please enter n: ";         cin >> n;         //populate num list         for(int i = 0; i < n; i++)         {                 primes.push_back(i);         }         //move through array, eliminating multiples         for(int i = 0; i < primes.size(); i++)         {                 numToCheck = primes[i];                 //dont check already marked                 if(numToCheck > 1)                 {                         //removes multiples                         for(int j = numToCheck; j < primes.size(); j += numToCheck)                         {                                 //check we aren't removing the prime                                 if(j == i)                                         continue;                                 primes[j] = 0;                         }                 }         }         primes.erase(std::remove(primes.begin(), primes.end(), 0), primes.end());         for(int i = 0; i < primes.size(); i++)         {                 cout << primes[i] << endl;         }```
• 07-23-2009
anon
Code:

```                        //removes multiples                         for(int j = numToCheck; j < primes.size(); j += numToCheck)                         {                                 //check we aren't removing the prime                                 if(j == i)                                         continue;```
What if you started from numToCheck + numToCheck to avoid removing the prime?

Actually you can safely start from numToCheck * numToCheck. If the prime is 3 then 6 is already crossed out as 2 * 3, if the prime is 5 then 2 * 5, 3 * 5, 4 (2 * 2) * 5 are already crossed out etc.

Perhaps you can also note that every second number to check is divisible by 2, hence crossed out. So you could also increment by NumToCheck * 2 (except for 2 which is a special case).