Sieve of Eratosthenes

Linear sieve computing primes, smallest prime factor (SPF), Euler's totient, and Mobius function in O(n).

[Number Theory]|

Jul 9, 2026

|explanatory_notes.md|

#sieve#prime#number-theory#totient#mobius

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

vector<bool> sieve(int n) {
  vector<bool> is_prime(n + 1, true);
  is_prime[0] = is_prime[1] = false;
  for (ll i = 2; i * i <= n; i++) {
    if (is_prime[i]) {
      for (ll j = i * i; j <= n; j += i) {
        is_prime[j] = false;
      }
    }
  }
  return is_prime;
}

vector<int> get_primes(vector<bool>& is_prime) {
  vector<int> primes;
  for (int i = 2; i < (int)is_prime.size(); i++)
    if (is_prime[i]) {
      primes.push_back(i);
    }
  return primes;
}

void Solve() {
  // write your code here
}

int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int t = 1;
  // cin >> t;
  while (t--) Solve();
  return 0;
}

38 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Sieve of Eratosthenes — Primality Testing

Quick Start (ECPC)

void Solve()
{
    int n; cin >> n;
    auto is_prime = sieve(n);
    int q; cin >> q;
    while (q--) {
        int x; cin >> x;
        cout << (is_prime[x] ? "YES" : "NO") << "\n";
    }    auto primes = get_primes(is_prime);
    cout << "count: " << primes.size() << "\n";
}

Functions

sieve(n) — returns vector, is_prime[i] for 0..n

get_primes(is_prime) — returns vector, all primes from is_prime

Notes

O(n log log n) time, O(n) space.

sieve(n) builds is_prime[0..n].

get_primes() iterates the boolean array and collects primes.

Use for: primality checks, prime factorization, primes up to 1e6-1e7.