Sieve Of Eratosthenes C++ Using Set Help

[Deadweight77]

As suggested in the title, I need some help with my Sieve of Eratosthenes program to remove multiples of prime numbers. I figured that line 16 would help me there, but I was wrong and need some assistance.

  #include <iostream>
#include <set>

using std::set;

void sieve(set<int>& s, int n)
{
	
	for (int i = 2; i <= n; i++)
	{
		if (i % 2 != 0)//getting the all the odd numbers
		{
			s.insert(i);
			for (int j = 2;  j <= n;j++)//after getting odd numbers, I must eliminate the multiples of said odd numbers
			{
				s.erase(i*j);
			}
		}
	}
	
}

void print_primes(const set<int>& s)
{
	for (auto it = s.begin(); it != s.end(); ++it)
	{
		std::cout << " " << *it;
	}
}


int main()
{
	set<int>s;
	int num;
	std::cout << "Upper limit for the set of primes: :";
	std::cin >> num;
	sieve(s, num);
	print_primes(s);
	return 0;
}

[lastchance]

You seem to be erasing things ... that were never there!

Best idea - don't use a set!

[Deadweight77]

I forgot to mention that this is a part on an assignment given to me, so I have no choice but to use a set I'm afraid.

[seeplus]

For the Sieve, don't you have to first generate the set of possible numbers, then repeatedly 'mark' those to be removed until no more can be marked? What's left unmarked are the primes?

See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[Deadweight77]

Yes, What I tried to do above was to insert all the numbers from a given range (i) and erase the multiples of the inserted values from line 16. I'm still trying to figure out why I'm erasing nothing. Perhaps because I never inserted j?

[dhayden]

What I tried to do above was to insert all the numbers from a given range (i)

I don't see any code that does this.

Also, the idea of the sieve is that after you erase a bunch of number, you remove them from consideration. So once you erase the multiples of 3, you shouldn't check them. What this really means is that your outer loop should go through the set, not just the numbers from 1 to n.

[lastchance]

Remove lines 11, 12, 13 and 18.

Between lines 37 and 38 insert all numbers from 2 to num inclusive in the set.

Then it “works”, but it’s hopelessly inefficient.

[jonnin]

for (int i = 2; i <= n; i++)
{
if (i % 2 != 0)//getting the all the odd numbers
{

Is the same as
insert(2)
for(int i = 3; i < = n; i+=2)
saving an if comparison and a modulo etc lots of do-nothing work.
if you are allowed to use a vector of bool, it would be faster / better to do the work in that and afterwards insert to the set. If you can't use anything else, it would still be better to somehow only insert to the set the primes and not erase at all, if you can rig the code that way. I can't think of a good way to do that, though...

[salem c]

Also cross-posted here -> https://www.dreamincode.net/forums/topic/420104-sieve-of-eratosthenes-c-using-set-help/

[lastchance]

Here you go @Deadweight77. It strictly fulfils the condition of "using" a std::set.

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
using namespace std;


set<int> sieve( int N )
{
   vector<bool> prime( 1 + N, true );
   prime[0] = prime[1] = false;
   for ( int i = 2, imax = sqrt( N + 0.1 ); i <= imax; i++ )
   {
      if ( prime[i] )
      {
         for ( int j = i * i; j <= N; j += i ) prime[j] = false;
      }
   }
   set<int> result;
   for ( int i = 2; i <= N; i++ ) if ( prime[i] ) result.insert( i );
   return result;
}


int main()
{
   set<int> S = sieve( 100 );
   for ( int i : S ) cout << i << ' ';
}

[dhayden]

Here is a version using the set exclusively:

#include <iostream>
#include <set>

using std::set;

void sieve(set<int>& s, int n)
{
    // Fill the set
    s.clear();			// make sure it's empty
    for (int i=2; i<=n; ++i) {
	s.insert(i);
    }

    // Starting with the first item (2), do the sieve.  You have to be
    // careful modifying a collection while iterating over it. Does
    // the modification invalidate the iterator? For a set, only
    // iterators pointing to the removed item are invalidated, so this
    // will work.
    for (auto i : s) {
	for (int j = 2; i*j <= n; j++) {
	    s.erase(i*j);
	}
    }
}

void print_primes(const set<int>& s)
{
	for (auto it = s.begin(); it != s.end(); ++it)
	{
		std::cout << " " << *it;
	}
}


int main()
{
	set<int>s;
	int num;
	std::cout << "Upper limit for the set of primes: :";
	std::cin >> num;
	sieve(s, num);
	print_primes(s);
	return 0;
}