Prime number generator with vector.erase()

[JackieJ]

we are required to generate prime numbers from 1 to 300 using the vector class and the vector erase function(v.erase(v.begin+1)). We are told to delete the non prime number from the list. So far I am only able to delete the even number. I know that using vector.erase() is probably not the most efficient way to create this program. But the assignment requires us to use it.
I have no idea how to continue. So far, my code looks like:

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

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

int main()
{
	int range;
	vector< int > v;
	cout << "Enter the upper range of number to display for prime numbers\n";
	cin >> range;
	if (range > 300 || range < 2)
	{
		cout << "Invalid range. Your range is not between 2 and 300\n";
	}
	else
	{
		Eratos(range, v);
	}
	return 0;
}

void Eratos(int &length, vector< int > &v)
{

	for (int i = 2; i < length; ++i)
	{
		v.push_back(i);

	}
		
	for (int i = 2; i < v.size();++i)
	{ 
		v.erase(v.begin() + i);
	}

	cout<< "Prime numbers are:\n";
	cout << v ;

}
ostream &operator <<(ostream& print, const vector<int> &v)
{
	int count = 1;
	for (unsigned int i = 0; i < v.size(); ++i)
	{
		print << setw(5)<< v[i];
		if (count % 10 == 0)
		{
			cout << '\n';
		}
		count++;
	}
	print << '\n';
	return print;
}

[shadowCODE]

add a function bool isPrime(int ) that will return true if prime and false if non prime.

Now change the for loop that does the erase to

for(int i = 2; i < v.size(); i++)
{
       if(!isPrime(i))
             v.erase(v.begin() + i);
}

[JackieJ]

shadowCODE, can you explain further. After implementing the bool function.
Now i have:

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

void Eratos(int &length, vector< int > &);
ostream &operator<< (ostream &, const vector <int>&);
bool isPrime(int);
int main()
{
	int range;
	vector< int > v;
	cout << "Enter the upper range of number to search for prime numbers\n";
	cin >> range;
	if (range > 300 || range < 2)
	{
		cout << "Invalid range. Your range is not between 2 and 300\n";
	}
	else
	{
		Eratos(range, v);
	}
	return 0;
}


void Eratos(int &length, vector< int > &v)
{

	for (int i = 2; i < length; ++i)
	{
		v.push_back(i);
	}
	for (int i = 2; i < v.size(); i++)
	{
		if (isPrime(i)==false)
		{
			v.erase(v.begin() + i);
		}
	}
	
	cout<< "Prime numbers are:\n";
	cout << v ;
}

ostream &operator <<(ostream& print, const vector<int> &v)
{
	int count = 1;
	for (unsigned int i = 0; i < v.size(); ++i)
	{
		print << setw(5)<< v[i];
		if (count % 10 == 0)
		{
			cout << '\n';
		}
		count++;
	}
	print << '\n';
	return print;
}
bool isPrime(int i)
{
	for (int j = 2; j < i; j++)
	{
		if (i%j == 0)
		{
			return false;
		}
		return true;
	}
}

it still doesn't work as expected.

[Yanson]

Your isPrime function doesn't work properly. Your return statement on line 70 should be outside the loop. There are lots of posts about making an isPrime function is would look at some of those.

[keskiverto]

Are you allowed to use the remove-erase idiom?

[shadowCODE]

OK so this is the problem with your code.

Firstly, put the return true outside the loop.

A bigger loop hole is the fact that fucntion isPrime(int) does not check all elements of the vector.
Example.

sample = ...... 8, 9,10, ....

when i reaches i = x where, sample[x] = 8 ,, it erases sample[x] and reduces the vector size by 1 (shifting all elements one place to the left) but the count of i is maintained as x

Hence, the next iteration, i = x+1 , where sample[i] = 10 and thus did not check 9 .

Add the line --i after the erase() inside the if statement so that isPrime() can recheck that position that position occupied by the new element.

[Rfernandez]

Shadow could you explain a little bit more what you mean about the --i line. I have tried putting it where you said and it doesnt seem to do much

[shadowCODE]

Firstly, the second for loop in the [code ] Eratos [/code] function should start from [code ] i = 0 [/code] and then in then isPrime() should be isPrime(v.at(i)) and not isPrime(i) .

Run this code that explains why you have to add --i .

#include <iostream>
#include <vector>
#include <iomanip>
#include <cstdlib>

using namespace std;

void Eratos(int &length, vector< int > &);
ostream &operator<< (ostream &, const vector <int>&);
bool isPrime(int);
int main()
{
	int range;
	vector< int > v;
	range = 10;
	if (range > 300 || range < 2)
	{
		cout << "Invalid range. Your range is not between 2 and 300\n";
	}
	else
	{
		Eratos(range, v);
	}
	return 0;
}


void Eratos(int &length, vector< int > &v)
{

	for (int i = 2; i < length; ++i)
	{
		v.push_back(i);
	}

	for (int i = 0; i < v.size(); i++)
	{
	    cout<<endl<<v;
	    cout<<"\nChecking "<<v.at(i) <<" , i = "<<i<<endl<<endl;
		if (isPrime(v.at(i))==false)
		{
			v.erase(v.begin() + i);
                        //add --i here after you understand why u need to add it
		}
	}

	cout<< "Prime numbers are:\n";
	cout << v ;
}

ostream &operator <<(ostream& print, const vector<int> &v)
{
	int count = 1;
	for (unsigned int i = 0; i < v.size(); ++i)
	{
		print << setw(5)<< v[i];
		if (count % 10 == 0)
		{
			cout << '\n';
		}
		count++;
	}
	print << '\n';
	return print;
}
bool isPrime(int i)
{
	for (int j = 2; j < i; j++)
	{
		if (i%j == 0)
		{
			return false;
        }
    }
    return true;
}

You realise that, if erase() erases an element in an index, then the new element that fills that index is not checked by isPrime() .

In the example above, when isPrime() is checking 4, i = 2.
When it erases 4( position 2), 5 replaces that position. But then i goes to 3 in the next iteration. Hence did not check 5( in position 2) that replaced 4.

Adding --i will recheck the new element in the position that was just erased.

[Rfernandez]

oh wow that explained it so well. thank you so much for your help

[shadowCODE]

welcome