What is a Prime Number?

A prime is an integer strictly larger than one that is divisible only by one and by itself.

So to check whether n is prime or not, the basic idea is:

• Try all numbers from 2 → n-1
• If any number divides n, then n is composite
• Otherwise, n is prime

Naive Code

bool is_prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

Optimization: Why Only Check Until √n ?

Example: n = 16

Divisors:

• 1 × 16
• 2 × 8
• 4 × 4
• 8 × 2
• 16 × 1

Notice something?

After reaching 4 = sqrt(16), the divisors start repeating.

✔️ This means we only need to check divisibility up to sqrt(n).

Optimized Prime Check

#define ll long long

bool is_prime(ll n) {
    if (n <= 1) return false;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

The Sieve of Eratosthenes — O(n log log n)

Imagine numbers from 2 → 20:

1  2  3  4
5  6  7  8
9 10 11 12
13 14 15 16
17 18 19 20

Idea

1. Assume all numbers are prime
2. Start from 2
3. Eliminate all multiples of 2
4. Move to the next number that is still marked prime
5. Eliminate all its multiples
6. Continue…

At the end, all remaining true entries are primes.

Sieve Code

const int N = 1e6 + 5;
vector<bool> prime(N, true);

void sieve() {
    prime[0] = prime[1] = false;
    for (int i = 2; i * i < N; i++) {
        if (prime[i]) {
            for (int j = i * i; j < N; j += i) {
                prime[j] = false;
            }
        }
    }
}

Complexity Intuition

Removing all multiples of:

• 2 → n/2
• 3 → n/3
• 4 → n/4
• 5 → n/5
• …
• n → n/n

Total work:

n(1/2 + 1/3 + 1/4 + ... + 1/n) = n log(n)

But composite numbers contribute less, giving final:

Sieve = O(n log log n)

Get All Divisors of n in O(√n)

vector<ll> divisors(ll n) {
    vector<ll> ret;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i != n / i) ret.push_back(n / i);
        }
    }
    return ret;
}

Count Prime Divisors for All Numbers (Divisor Sieve)

const int N = 1e6 + 5;
int d[N];   // d[i] = number of prime divisors of i

void sieveDivisors() {
    for (int i = 2; i < N; i++) {
        if (d[i] == 0) {  // i is prime
            for (int j = i; j < N; j += i) {
                d[j]++;
            }
        }
    }
}

Prime Factorization in O(√n)

vector<pair<ll, ll>> primeFactors(ll n) {
    vector<pair<ll, ll>> ret;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ll cnt = 0;
            while (n % i == 0) {
                cnt++;
                n /= i;
            }
            ret.push_back({i, cnt});
        }
    }
    if (n != 1) ret.push_back({n, 1});
    return ret;
}

Conclusion

You learned:

Basic prime checking

Optimizing with sqrt(n)

Sieve of Eratosthenes

Time complexity intuition

Getting divisors

Counting prime divisors

Prime factorization