Erastosfen Sieve

mail@pastecode.io avatar
unknown
c_cpp
3 years ago
410 B
5
Indexable
Never
class EratosfenSieve
{
public:
  vector<int> used;
  vector<int> pr;
  int N;
  EratosfenSieve(int N){
    this->N = N;
    used.resize(N + 1);
  }

  void sieve()
  {
    pr.reserve(N / 10);
    for (long long i = 2; i <= N; i++)
    {
      if (!used[i])
      {
        pr.push_back(i);
        for (long long j = i * i; j <= N; j += i)
          used[j] = true;
      }
    }
  }
};