Prime Sieve

Sieve of Eratosthenes

void sieve(int32_t n) {
    std::vector<bool> is_prime(n, true);
    std::vector<int32_t> primes;
    for (int64_t i = 2; i < n; ++i) {
        if (!is_prime[i]) continue;
        primes.push_back(i);
        for (auto j = i * i; j < n; j += i) is_prime[j] = false;
    }
}

Time Complexity: $O(n \ln \ln n)$

The below analysis is for the case when the highlighted line above starts with j = 2 * i.

To prove this, notice that the number of iterations are something like $O(n)+\sum_{p \le n} \frac{n}{p}$ where $p$ is a prime. Well, Merten’s Second Theorem states that $\sum_{p \le n} \frac{1}{p} = \ln \ln n + O(1)$

Linear Sieve

std::vector<int32_t> linear_sieve(int32_t n) {
    std::vector<int32_t> primes;
    std::vector<int32_t> lowest_prime(n, 0);
    for (int64_t i = 2; i < n; ++i) {
        if (lowest_prime[i] == 0) {
            primes.push_back(i);
            lowest_prime[i] = i;
        }
        for (auto const& p : primes) {
            if (p > lowest_prime[i]) break;
            if (auto j = i * p; j < n) {
                lowest_prime[j] = p;
            }
        }
    }
    return lowest_prime;
}

Time Complexity: $O(n)$

Segmented Sieve

vector<int> prime_divisors[N];

/* assume sieve(N) is already called. */
void segmentedSieve(int a, int b) {
  for (ll x = a; x <= b; ++x) prime_divisors[x - a].clear();
  for (const auto& p: primes) {
    for (ll x = ((a + p - 1) / p) * p; x <= b; x += p) {
      /* p is a prime divisor of x. Do anything with this fact. */
      prime_divisors[x - a].push_back(p);
    }
  }
}

/* If a prime greater than sqrt(N) divides x then that prime will be missing from prime_divisors[x].
 * You can find that by the expressions x / (product of all p in prime_divisors[x])
 */