There's no major flaw in your code - it works, but it's a bit bulky.
The basic logic is:
- Fill a vector, named
sieve
, with 1s (chars to save memory) - For each prime element in the first vector, mark all of its multiples as prime
- Add every prime element int he first vector the the
retVector
, and return the vector of all primes up untillimit
Another working implementation of the sieve in c++ might look something like the following:
vector<long long> sieve(unsigned long long & limit)
{
vector<char> sieve(limit, '1');
vector<long long> retVector;
for (long long i = 0; i < limit; i++)
sieve[i] = 1;
for (long long i = 2; i < limit; i++) {
if (sieve[i] == 1) {
for (long long j = i*i; j < limit; j += i)
sieve[j] = 0;
}
}
for (long long i = 2; i < limit; ++i) if (sieve[i] == 1) retVector.push_back(i);
return retVector;
}