Originally Posted by
iMalc
Don't use a list for this.
Lists have the overhead of two pointers per item, which is pretty large considering you really only need a single bit to indicate whether a number is marked off or not.
With a list you obviously find yourself having to skip over many items to get to each multiple of i. With a vector you just go straight to that item and mark it off.
Apart from 2 (special case), you only need consider odd numbers.
Actually, the list of primes is better in this case. Since you dont' know how many primes will be in the range [2,max], so you have no way to reserve the size for the vector. And as the number of primes grow, the vector may have to be reallocated which is a waste of time. The seive can be implemented as an array to type bool instead of unsigned long.
Code:
list<unsigned long> prime_gen(unsigned long max)
vector<bool> seive(max, true);
list<unsigned long> primes;
// then iterate over the range [2,max]
for ( unsigned long i = 2; i <= max; ++i)
if( seive[i] )
{
primes.push_back(i)
// then mark off the multiples;
for ( unsigned long j = i; j <= max; j+=i)
seive[j]=0
}
}
There may be a faster way.