Thread: 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?

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());

Thanks for the comments.

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?

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...?

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.

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).