Deleting Vector objects in a for loop

This is a discussion on Deleting Vector objects in a for loop within the C++ Programming forums, part of the General Programming Boards category; Hi all, I am currently trying to implement a Sieve of Eratostheneses in C++ as part of a book I ...

  1. #1
    Apprentice Swordsman's Avatar
    Join Date
    Apr 2007
    Posts
    38

    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?
    Last edited by Swordsman; 07-23-2009 at 08:07 AM.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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());
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Apprentice Swordsman's Avatar
    Join Date
    Apr 2007
    Posts
    38
    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?
    Last edited by Swordsman; 07-23-2009 at 09:39 AM.

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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 might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Apprentice Swordsman's Avatar
    Join Date
    Apr 2007
    Posts
    38
    Thanks for your continued help.

    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?

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    Apprentice Swordsman's Avatar
    Join Date
    Apr 2007
    Posts
    38
    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; 
    	}

  8. #8
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Creating and deleting directories and deleting files
    By fguy817817 in forum C Programming
    Replies: 1
    Last Post: 04-08-2009, 08:26 AM
  2. deleting nodes in a linear list
    By sudhanshu_nsit in forum C++ Programming
    Replies: 7
    Last Post: 06-25-2006, 03:00 AM
  3. Deleting dynamically allocated objects
    By Daniel Jurnove in forum C++ Programming
    Replies: 3
    Last Post: 11-07-2002, 03:30 AM
  4. Deleting Records from a structure
    By Simon in forum C Programming
    Replies: 5
    Last Post: 09-12-2002, 12:28 AM
  5. need help deleting a deleting a struct from file
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 05-20-2002, 06:38 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21