Article: Linear Sieve

Problem:

It is possible to calculate the primes without saving an array of the least prime factors thus making the memory constraints of the algorithm the same as the classic sieve:

vector<bool> lp(N+1);
...
if (lp[i] == false) {
    pr.push_back(i);
}
for (int j = 0; i * pr[j] <= N; ++j) {
    lp[i * pr[j]] = true;
    if (i%pr[j] == 0) {
        break;
    }
}