Prime Numbers

[bluegray]

I need to remove all prime numbers from the set. I can get the first loop to remove all the even numbers. I tried using two for loops but when i did that i deleted every number.

What am i doing wrong?

#include <cstdlib>
#include <iostream>
#include <string>
#include <set>
#include <iomanip>

using namespace std;

void print_primes(const set<int>& s)
{
	int i = 0;
	
	set<int>::const_iterator it;
	
	for(it = s.begin(); it != s.end(); it++ ){
		cout << *it << " ";
		if (++i >= 10)
		{
			i = 0;
			cout << endl;
		}
		
	}
	
	cout << endl;
}
void sieve(set<int>& s, int n)
{
	set<int>::const_iterator it;
	int m;
	int key = 2;
	
	for(int i = 2; i <= n; i++) s.insert(i);
	
	for(int sum = 1; sum <= n; sum++)
		{
			m = key * sum;
			s.erase(m);
		}
	
}
int main()
{
	set<int> s;
	
	int upperLimit;
	
	cout << "Enter the value of the upper limit: ";
	cin >> upperLimit;
	
	sieve(s, upperLimit);
	print_primes(s);
}

[jpeg]

If you remove all even and odd numbers, then you remove all the numbers of course.

I definitely won't claim that it's the best way to do a prime calculation, but what I would do is modulo the number with all the numbers less than itself in the list. If they all return 0, then you have a prime number, otherwise, delete it from the list.

[xabnu]

what jpeg said.

only make sure to start at the lowest numbers, or it'll take forever.

[int main]

You can speed up the process by testing the modulo only for all uneven divisors smaller then half the number in question.
e.e. if you test 17 it is sufficient to test all division from 3 to 7 because 1 does not count, two is not necessary since you already have removed the even numbers and anything above 8 can not be a divisor that could possibly return an integer.
4, 6 and 8 cannot be divisors because a multiplication with either of the three would returnn an even number.

int main

[Fluffy Bunny]

Even better, you only need to test divisors up to the square root of the number you are testing. That is, if x has no factors <= sqrt(x), then x is prime.

[jsmith]

It looks like the author wants to use the Sieve of Eratosthenes algorithm for finding prime numbers. Reference http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

You will need nest for-loops to implement this algorithm which is explained well at the above link.

You have implemented only one of the loops. Currently, your code only removes all multiples of 2.

[bluegray]

Ya i was trying to use Seive of Eratosthenes. thanks for the link it helped.

This is how i ended up doing it

void sieve(set<int>& s, int n)
{
	set<int>::const_iterator it;
	int i;
	//fill the set with ints 2, 3, ... , n
	for(int fill = 2; fill <= n; fill++) s.insert(fill);
	
	for(int m = 2; m * m <= n; m++) 
	{
		//check if m is still in the set
		if(s.find(m) != s.end())
		{
			i = 2 * m;
				while(i <= n)
				{
					s.erase(i);
					i += m;
				}
		}
	}
}