This lesson includes an expert video walkthrough — purchase once for a full year of unlimited replays to master every key point 🎬

Prime Numbers

Knowledge Summary

Prime Checking

For n > 1, check whether it has any factor from 2 to √n:

1bool isPrime(int n) {
2    if (n < 2) return false;
3    for (int i = 2; i * i <= n; i++)
4        if (n % i == 0) return false;
5    return true;
6}

Time complexity: O(√n)

Sieve of Eratosthenes

Find all prime numbers in the range 1 to n:

1bool notPrime[N];
2void sieve(int n) {
3    notPrime[0] = notPrime[1] = true;
4    for (int i = 2; i * i <= n; i++)
5        if (!notPrime[i])
6            for (int j = i * i; j <= n; j += i)
7                notPrime[j] = true;
8}

Time complexity: O(n log log n)

Linear Sieve (Euler Sieve)

Each composite number is marked exactly once by its smallest prime factor:

1int primes[N], cnt = 0;
2bool notPrime[N];
3void linearSieve(int n) {
4    for (int i = 2; i <= n; i++) {
5        if (!notPrime[i]) primes[cnt++] = i;
6        for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
7            notPrime[i * primes[j]] = true;
8            if (i % primes[j] == 0) break;
9        }
10    }
11}

Time complexity: O(n)

Frequently Tested Knowledge Points

There are 25 prime numbers below 100
There are 168 prime numbers below 1000
2 is the only even prime
1 is neither prime nor composite
Distribution of primes: there are about n/ln(n) primes less than or equal to n