Linear Sieve

class LinearSieve
{
public:
  vector<int> lp, pr;
  int N;
  LinearSieve(int N){
    this->N = N;
    lp.resize(N + 1);
  }
  void linearSieve()
  {
    pr.reserve(N / 10);
    for (int i = 2; i <= N; i++)
    {
      if (lp[i] == 0)
      {
        lp[i] = i;
        pr.push_back(i);
      }
      for (int j = 0; j < pr.size() && pr[j] <= lp[i] && i * pr[j] <= N; j++)
        lp[i * pr[j]] = pr[j];
    }
  }
};