#include "sieve.hh"
#include <cmath>
#include <cstring>

[[nodiscard]] std::vector<int> segmentedSieve(std::size_t size) {
  const size_t s = sqrt(size);
  const auto primes = sieve3(s);
  std::vector<int> r{primes};
  std::vector<int> r2;

  size_t l = s;
  size_t h = l + s;
  unsigned char *n = (unsigned char *)malloc(s);

  while (l < size) {

    memset(n, false, s);

    for (const auto prime : primes) {
      // find the first number divisible by prime
      std::size_t f = (l / prime) * prime;
      if (f < l)
        f += prime;

      for (std::size_t i = f; i < h; i += prime)
        n[i - l] = true;
    }
    for (std::size_t i = 0; i < s; ++i)
      if (n[i] == false)
        r2.emplace_back(i + l);

    l += s;
    h += s;
  }

  free(n);

  r.reserve(r.size() + r2.size());
  r.insert(r.end(), r2.begin(), r2.end());
  return r;
}