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;    }}