Prime Numbers and Sieve of Eratosthenes

Prime Numbers: Brute Force and the Sieve of Eratosthenes

A prime number is an integer greater than 1 that has exactly two positive divisors: 1 and itself. The sequence of primes begins:

$$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, \dots$$

An integer greater than 1 that has more than two divisors is called a composite number. The number 1 is neither prime nor composite.

---

1. Brute-Force Prime Generation

Given an integer $n \ge 2$, we wish to list all primes between $2$ and $n$.

Definition-Based Brute Force

For every candidate integer $x$ from $2$ to $n$, test whether any divisor $d$ from $2$ to $x - 1$ divides $x$ evenly:

BruteForcePrimes(n):
    // Input: Integer n >= 2
    // Output: List of all prime numbers <= n
    primes = empty list
    for x = 2 to n do:
        isPrime = true
        for d = 2 to x - 1 do:
            if x mod d == 0 then:
                isPrime = false
                break
        if isPrime then:
            primes.append(x)
    return primes

Efficiency Analysis:

• In the worst case (when $x$ is prime), the inner loop runs $x - 2$ iterations.
• Total comparisons:

$$\sum_{x=2}^n (x - 2) = \frac{(n-2)(n-1)}{2} = \Theta(n^2)$$

• Time Complexity: $O(n^2)$
• Space Complexity: $O(1)$ auxiliary space.

Square-Root Optimization

If $x = a \times b$, at least one factor must satisfy $a \le \sqrt{x}$. If no divisor is found up to $\lfloor \sqrt{x} \rfloor$, $x$ must be prime:

OptimizedBruteForcePrimes(n):
    primes = empty list
    for x = 2 to n do:
        isPrime = true
        for d = 2 to floor(sqrt(x)) do:
            if x mod d == 0 then:
                isPrime = false
                break
        if isPrime then:
            primes.append(x)
    return primes

Efficiency Analysis:

• Inner loop runs at most $\sqrt{x}$ times.
• Summing over all $x \le n$:

$$\sum_{x=2}^n \sqrt{x} \approx \int_1^n x^{1/2} dx = \frac{2}{3} n^{3/2} = \Theta(n\sqrt{n})$$

• Time Complexity: $O(n\sqrt{n})$ or $O(n^{1.5})$.

---

2. Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient and substantially more efficient algorithm that systematically eliminates multiples of primes rather than repeatedly testing division.

Algorithm Strategy

1. Initialize a boolean array A[2..n] where every entry is initially true.
2. For $p = 2, 3, \dots, \lfloor \sqrt{n} \rfloor$:
   • If A[p] is still true, then $p$ is prime.
   • Cross out all multiples of $p$ starting at $p^2$:
   $$p^2, p^2 + p, p^2 + 2p, \dots \le n$$ (Note: Any multiple $k \times p$ with $k < p$ has already been crossed out by smaller prime factors!)
3. Any number $x$ remaining true at the end is prime.

SieveOfEratosthenes(n):
    // Input: Integer n >= 2
    // Output: Array of all prime numbers <= n
    for p = 2 to n do A[p] = true

    for p = 2 to floor(sqrt(n)) do:
        if A[p] == true then:
            j = p * p
            while j <= n do:
                A[j] = false
                j = j + p

    primes = empty list
    for p = 2 to n do:
        if A[p] == true then:
            primes.append(p)
    return primes

Visual Trace: Sieve for $n = 25$

$\lfloor \sqrt{25} \rfloor = 5$. We only need outer loop passes for $p = 2, 3, 5$:

Number	After $p=2$ (eliminate $\ge 4$)	After $p=3$ (eliminate $\ge 9$)	After $p=5$ (eliminate $\ge 25$)	Final Prime Status
2	Prime	Prime	Prime	Prime
3	Prime	Prime	Prime	Prime
4	Eliminated ($2 \times 2$)	-	-	Composite
5	Prime	Prime	Prime	Prime
6	Eliminated ($2 \times 3$)	-	-	Composite
7	Prime	Prime	Prime	Prime
9	Undecided	Eliminated ($3 \times 3$)	-	Composite
11	Prime	Prime	Prime	Prime
13	Prime	Prime	Prime	Prime
15	Eliminated ($2 \times \dots$)	Eliminated ($3 \times 5$)	-	Composite
25	Undecided	Undecided	Eliminated ($5 \times 5$)	Composite

Time & Space Complexity

• Time Complexity:

$$\sum_{p \le \sqrt{n}} \frac{n}{p} \approx n \sum_{p \le n} \frac{1}{p} = \Theta(n \log \log n)$$

Because $\log \log n$ grows exceptionally slowly, this is virtually linear in practice.

• Space Complexity: $\Theta(n)$ for the boolean table A[2..n].

---

Comparison Summary

Algorithm	Method	Worst-Case Time	Auxiliary Space	Key Advantage
Brute Force (Definition)	Test all $d < x$	$\Theta(n^2)$	$\Theta(1)$	Simple to implement
Brute Force (Optimized)	Test all $d \le \sqrt{x}$	$\Theta(n\sqrt{n})$	$\Theta(1)$	No memory overhead
Sieve of Eratosthenes	Eliminate multiples from $p^2$	$\Theta(n \log \log n)$	$\Theta(n)$	Vastly faster for ranges

---

Exercises

Exercise 1

In the Sieve of Eratosthenes, why does crossing out multiples of $p$ start at $p^2$ rather than $2p$?

Show solution ↓Hide solution ↑

Solution

Any multiple of $p$ smaller than $p^2$ can be written as $k \times p$ where $k < p$.

Since $k < p$, $k$ must have a prime divisor $q \le k < p$. Consequently, this number $k \times p$ was already crossed out when the algorithm processed the smaller prime $q$.

Starting at $p^2$ eliminates redundant crossing out operations.

Exercise 2

Calculate the number of operations required by the Sieve of Eratosthenes vs. the Brute-Force definition algorithm for $n = 10{,}000$.

Show solution ↓Hide solution ↑

Solution

• Brute Force: $\approx \frac{n^2}{2} = \frac{10^8}{2} = 50{,}000{,}000$ operations.
• Sieve of Eratosthenes: $\approx n \log_e (\log_e n) = 10{,}000 \times \ln(\ln(10000)) \approx 10{,}000 \times \ln(9.21) \approx 10{,}000 \times 2.22 \approx 22{,}200$ operations.

The Sieve is over 2,200 times faster for $n = 10{,}000$.