help about sieve algorithm
I wrote a program to print all the prime numbers from 1 to a given number, but this program is not efficient to deal with large number. Given a number such as 99999, it takes about 1min to finish this job. Could you please give me some suggestion on how to make this program more efficient? Thanks in advance.
Code:
#include <list>
#include <vector>
#include <iostream>
#include <iomanip>
using std::list;
using std::vector;
using std::cout;
using std::cin;
using std::endl;
using std::setw;
int main()
{
list<unsigned long> numbers;
vector<unsigned long> prime;
unsigned long range;
// ask the user to input the range
cout << "I wanna know the prime numbers from 1 to : ";
cin >> range;
prime.push_back( 2L ); // 2 is the first one to sieve.
for ( unsigned long i = 3; i <= range; ++i ) {
if ( i % 2 ) { // multiples of 2 is no need to insert into the list
numbers.push_back( i );
}
}
unsigned long tmp;
while ( !numbers.empty() ) {
tmp = numbers.front();
prime.push_back( tmp ); // push the first element of the list into the vector
numbers.pop_front(); // remove the first element from the list
for ( std::list<unsigned long>::iterator iter = numbers.begin();
iter != numbers.end(); ++iter ) {
if ( *iter % tmp ) {
continue;
}
iter = numbers.erase( iter ); // remove multiples of tmp from the list
}
}
// print the prime numbers
unsigned long j = 0;
for ( std::vector<unsigned long>::iterator it = prime.begin();
it != prime.end(); ++it ) {
cout << setw(12) << *it << ' ';
if ( !(++j % 6) ) {
cout << '\n';
}
}
cout << endl;
return 0;
}