Prime Numbers

A Prime Number is a positive integer greater than 1 that is divisible only by 1 and itself.

Checking for Prime

Basic Method $O(\sqrt{n})$

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

Why Only $\sqrt{n}$?

If $n = a \times b$ and $a \leq b$, then $a \leq \sqrt{n}$

Therefore, if no divisor $\leq \sqrt{n}$ exists, then $n$ is prime.

Sieve of Eratosthenes

Find all primes from 2 to n in $O(n \log \log n)$

Method

1. Create array isPrime[0..n] initialized to true
2. Start from 2, mark all its multiples as false
3. Move to the next number that is still true and repeat

const int MAXN = 1e7 + 5;
bool isPrime[MAXN];
vector<int> primes;

void sieve(int n) {
    fill(isPrime, isPrime + n + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    // Store primes in vector
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) primes.push_back(i);
    }
}

Visualization

Initial: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...

After marking multiples of 2:
         2 3 X 5 X 7 X 9 X  11 X  13 X  15 ...

After marking multiples of 3:
         2 3 X 5 X 7 X X X  11 X  13 X  X  ...

Remaining primes: 2, 3, 5, 7, 11, 13, ...

Linear Sieve $O(n)$

Faster sieve where each composite number is marked only once.

const int MAXN = 1e7 + 5;
int spf[MAXN]; // smallest prime factor
vector<int> primes;

void linearSieve(int n) {
    fill(spf, spf + n + 1, 0);
    
    for (int i = 2; i <= n; i++) {
        if (spf[i] == 0) { // i is prime
            spf[i] = i;
            primes.push_back(i);
        }
        
        for (int p : primes) {
            if (p > spf[i] || (long long)i * p > n) break;
            spf[i * p] = p;
        }
    }
}

Additional Benefits

spf[i] stores the smallest prime factor, enabling fast factorization.

vector<int> factorize(int n) {
    vector<int> factors;
    while (n > 1) {
        factors.push_back(spf[n]);
        n /= spf[n];
    }
    return factors;
}

Segmented Sieve

Find primes in range [L, R] when R is very large (e.g., $10^{12}$) but range width R - L doesn’t exceed $10^6$.

vector<long long> segmentedSieve(long long L, long long R) {
    // First find primes up to sqrt(R)
    int sqrtR = sqrt(R) + 1;
    sieve(sqrtR);
    
    // Create array for range [L, R]
    vector<bool> is_prime(R - L + 1, true);
    
    for (int p : primes) {
        if ((long long)p * p > R) break;
        
        // Find first multiple of p that is >= L
        long long start = max((long long)p * p, ((L + p - 1) / p) * p);
        
        for (long long j = start; j <= R; j += p) {
            is_prime[j - L] = false;
        }
    }
    
    // Handle case when L = 1
    if (L == 1) is_prime[0] = false;
    
    vector<long long> result;
    for (long long i = 0; i <= R - L; i++) {
        if (is_prime[i]) result.push_back(L + i);
    }
    
    return result;
}

Prime Counting Function

$\pi(n)$ = count of primes $\leq n$

Approximation

$\pi(n) \approx \frac{n}{\ln n}$

n	$\pi(n)$	Approximation
$10^3$	168	145
$10^6$	78,498	72,382
$10^9$	50,847,534	48,254,942

Prime Gap

Distance between consecutive primes.

• For $n \leq 10^6$, gap doesn’t exceed 100
• For $n \leq 10^9$, gap doesn’t exceed 300

Primality Testing for Large Numbers

Miller-Rabin Primality Test

Test if $n$ is prime in $O(k \log^3 n)$ where $k$ is number of test rounds.

long long mulmod(long long a, long long b, long long m) {
    return (__int128)a * b % m;
}

long long powmod(long long a, long long b, long long m) {
    long long res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) res = mulmod(res, a, m);
        a = mulmod(a, a, m);
        b >>= 1;
    }
    return res;
}

bool millerRabin(long long n, long long a) {
    if (n % a == 0) return n == a;
    
    long long d = n - 1;
    int r = 0;
    while (d % 2 == 0) {
        d /= 2;
        r++;
    }
    
    long long x = powmod(a, d, n);
    if (x == 1 || x == n - 1) return true;
    
    for (int i = 0; i < r - 1; i++) {
        x = mulmod(x, x, n);
        if (x == n - 1) return true;
    }
    
    return false;
}

bool isPrimeLarge(long long n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;
    
    // Witnesses for n < 3,317,044,064,679,887,385,961,981
    vector<long long> witnesses = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    
    for (long long a : witnesses) {
        if (n == a) return true;
        if (!millerRabin(n, a)) return false;
    }
    
    return true;
}

Goldbach’s Conjecture

Every even integer greater than 2 can be expressed as the sum of two primes.

pair<int, int> goldbach(int n) {
    sieve(n);
    for (int p : primes) {
        if (isPrime[n - p]) {
            return {p, n - p};
        }
    }
    return {-1, -1}; // Should never happen
}

Example Problems

Problem 1: Count primes in a range

int countPrimes(int L, int R) {
    sieve(R);
    int count = 0;
    for (int i = L; i <= R; i++) {
        if (isPrime[i]) count++;
    }
    return count;
}

Problem 2: Find the k-th prime

int kthPrime(int k) {
    sieve(10000000); // Estimate that k-th prime is within this range
    return primes[k - 1];
}

Problem 3: Count distinct prime factors

int countDistinctPrimeFactors(int n) {
    linearSieve(n);
    set<int> factors;
    while (n > 1) {
        factors.insert(spf[n]);
        n /= spf[n];
    }
    return factors.size();
}

Summary

Algorithm	Complexity	Use Case
Basic Check	$O(\sqrt{n})$	Check single number
Sieve of Eratosthenes	$O(n \log \log n)$	Find all primes up to n
Linear Sieve	$O(n)$	Find primes + SPF
Segmented Sieve	$O((R-L) \log \log R)$	Primes in range [L, R]
Miller-Rabin	$O(k \log^3 n)$	Prime test for large n

💡 Tip: For problems requiring multiple prime checks, sieve first and store results in a vector.