Problem on article Linear Sieve

[ahmedosama20]

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

[adamant-pwn]

Thanks for the comment! Wouldn't it be slower on practice though? I imagine i % pr[j] operation would be much costlier than pr[j] == lp[i]. I guess we could still mention that it is an option, if you want to make a pull request about it, but I wouldn't use it as the main implementation?