Linear Sieve Solution O(n)


#1

vector Solution::sieve(int A) {

vector <int> pr;
vector <int> mark(A+1,0);
for(int i=2;i<=A;i++)
{
    if(mark[i]==0)
    pr.push_back(i);
    for(int j=0;j<pr.size() && pr[j]*i<=A;j++){
        mark[pr[j]*i]=1;
    }
}
return pr;

}