Prime number generator with vector.erase()

Sep 8, 2014 at 12:04am
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:



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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;
}
Last edited on Sep 8, 2014 at 12:44am
Sep 8, 2014 at 12:52am
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
1
2
3
4
5
for(int i = 2; i < v.size(); i++)
{
       if(!isPrime(i))
             v.erase(v.begin() + i);
}

Sep 8, 2014 at 4:49am
shadowCODE, can you explain further. After implementing the bool function.
Now i have:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#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.
Last edited on Sep 8, 2014 at 4:52am
Sep 8, 2014 at 8:12am
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.
Sep 8, 2014 at 8:27am
Are you allowed to use the remove-erase idiom?
Sep 8, 2014 at 9:13am
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.
Sep 10, 2014 at 9:25pm
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
Sep 10, 2014 at 10:16pm
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 .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#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.
Sep 10, 2014 at 10:49pm
oh wow that explained it so well. thank you so much for your help
Sep 10, 2014 at 11:45pm
welcome
Topic archived. No new replies allowed.