Prime Numbers & the Sieve of Eratosthenes

A prime number is an integer greater than 1 whose only divisors are 1 and itself (2, 3, 5, 7, 11, …). Two tasks dominate prime problems: testing one number for primality (do it in O(√n)) and listing every prime up to n with the Sieve of Eratosthenes (in O(n log log n)). This page covers both, plus the trial-division factorization that builds on them.

Testing a single number — trial division to √n

If n has a divisor larger than √n, it must also have one smaller than √n, so you only need to check up to the square root. Skip even numbers after 2 to halve the work.

bool isPrime(long long n) {
    if (n < 2) return false;
    if (n < 4) return true;            // 2 and 3
    if (n % 2 == 0) return false;
    for (long long i = 3; i * i <= n; i += 2)
        if (n % i == 0) return false;
    return true;
}

boolean isPrime(long n) {
    if (n < 2) return false;
    if (n < 4) return true;            // 2 and 3
    if (n % 2 == 0) return false;
    for (long i = 3; i * i <= n; i += 2)
        if (n % i == 0) return false;
    return true;
}

function isPrime(n) {
  if (n < 2) return false;
  if (n < 4) return true;             // 2 and 3
  if (n % 2 === 0) return false;
  for (let i = 3; i * i <= n; i += 2)
    if (n % i === 0) return false;
  return true;
}

def is_prime(n):
    if n < 2:
        return False
    if n < 4:
        return True          # 2 and 3
    if n % 2 == 0:
        return False
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

Pitfall: Use the condition i * i <= n, not i <= sqrt(n). Floating-point sqrt can round wrong near perfect squares and misclassify a number. In C++/Java, ensure i * i itself doesn’t overflow — use a 64-bit type when n can be large.

Finding all primes up to n — the Sieve of Eratosthenes

To list every prime up to n, don’t test each number separately. Instead, start assuming all are prime, then repeatedly cross out the multiples of each prime you find. Whatever survives is prime.

#include <vector>
std::vector<int> sieve(int n) {
    std::vector<bool> isComposite(n + 1, false);
    std::vector<int> primes;
    for (int i = 2; i <= n; i++) {
        if (!isComposite[i]) {
            primes.push_back(i);
            for (long long j = (long long)i * i; j <= n; j += i)
                isComposite[j] = true;
        }
    }
    return primes;
}

import java.util.*;
List<Integer> sieve(int n) {
    boolean[] isComposite = new boolean[n + 1];
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (!isComposite[i]) {
            primes.add(i);
            for (long j = (long) i * i; j <= n; j += i)
                isComposite[(int) j] = true;
        }
    }
    return primes;
}

function sieve(n) {
  const isComposite = new Array(n + 1).fill(false);
  const primes = [];
  for (let i = 2; i <= n; i++) {
    if (!isComposite[i]) {
      primes.push(i);
      for (let j = i * i; j <= n; j += i) isComposite[j] = true;
    }
  }
  return primes;
}

def sieve(n):
    is_composite = [False] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if not is_composite[i]:
            primes.append(i)
            for j in range(i * i, n + 1, i):
                is_composite[j] = True
    return primes

Going deeper: Starting the inner loop at i * i (not 2 * i) is the key optimization — every smaller multiple of i was already crossed out by a smaller prime. This is what gives the O(n log log n) runtime, which is nearly linear in practice.

Prime factorization

Once you can test or sieve primes, factoring is trial division that divides out each factor as you find it. The leftover (if greater than 1) is a single large prime factor.

#include <vector>
std::vector<long long> factorize(long long n) {
    std::vector<long long> factors;
    for (long long d = 2; d * d <= n; d++)
        while (n % d == 0) { factors.push_back(d); n /= d; }
    if (n > 1) factors.push_back(n); // leftover prime
    return factors;
}

import java.util.*;
List<Long> factorize(long n) {
    List<Long> factors = new ArrayList<>();
    for (long d = 2; d * d <= n; d++)
        while (n % d == 0) { factors.add(d); n /= d; }
    if (n > 1) factors.add(n); // leftover prime
    return factors;
}

function factorize(n) {
  const factors = [];
  for (let d = 2; d * d <= n; d++)
    while (n % d === 0) { factors.push(d); n /= d; }
  if (n > 1) factors.push(n); // leftover prime
  return factors;
}

def factorize(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)  # leftover prime
    return factors

Complexity

Task	Time	Space
`isPrime(n)`	O(√n)	O(1)
Sieve up to n	O(n log log n)	O(n)
Factorize n	O(√n)	O(log n) factors

When to use which

Use trial division to test a handful of numbers or factor one value. Use the sieve when you’ll query primality many times up to a fixed bound — precompute once, answer in O(1). Both lean on the GCD ideas and feed into modular arithmetic. Next: modular arithmetic and fast exponentiation.