Sieve of Eratosthenes

[blee93]

This is my failed attempt at creating the Sieve of Eratosthenes. Can anyone spot any problems? I just started to learn the STL, but the concept of iterators and the STL in general is really difficult for me.

-The input represents the number of cases. The variable m represents the lower bound and the variable n represents the upper bound.

#include <iostream>
#include <list>
#include <iterator>

using namespace std;

int main()
{
	int input, m, n;
	cin >> input;

	for (int i = 0; i < input; i++)
	{
		cin >> m >> n;
		list<int> numbers;
		if (m <= 1)
			m = 2;
		for (int j = m; j <= n; j++)
			numbers.push_back(j);

		list<int>::iterator it;
		for (it = numbers.begin(); it != numbers.end(); ++it)
			for (int k = *it; k <= n; k += (*it))
				numbers.remove(k);

        cout << "Primes between " << m << " and " << n << " are: ";
		copy(numbers.begin(),numbers.end(),ostream_iterator<int> (cout, "\n"));
	}
    return 0;
}

[blee93]

Bump!

[blee93]

Anyone?

[rubberman]

School exercise? First, state the problem clearly before you start coding. Second, write out the algorithm you are going to use as pseudo-code. Third, keep the actual code as simple as possible.

Sieve: generate array of prime numbers. A prime number is divisible only by 1 and itself. The numbers 1, 2, and 3 are prime. All even numbers other than 2 are not prime. So, we only have to consider odd numbers from 4 through the limit value.

Refinement: other than 5, all numbers that end in 5 are divisible by 5, hence not prime.

So, we have eliminated all numbers > 3 that end in 0, 2, 4, 6, or 8. We have also eliminated all numbers > 5 that end in 5. So, we only have to consider numbers > 5 that end in 3, 7, or 9. These are the only numbers that we need to check for divisibility by any of the previously discovered prime numbers < 1/2 of the number being considered.

Once we have generated our array of indicators (can be a bit-array for size, or numeric for speed) where 0 == !prime and 1 == prime, we can now create an algorithm to find prime factors for any number quite easily. I will leave that as an exercise for the reader... :-)

[Narue]

Bump!

I'll be happy to help you, after you explain what makes you so much more important than everyone else posting threads on this forum who got bumped down (not to mention one unlucky soul who fell off into the void of page 2 and will now never get help) so that your question could be brought back to the forefront.