Prime Finder

Background Knowledge

Prime numbers are natural numbers greater than 1 that have no positive divisors other than 1 and themselves. For example, 2, 3, 5, and 7 are primes, while 4 is composite (divisible by 2). Testing each number individually for primality via trial division—checking divisibility up to its square root—works for small ranges but becomes inefficient for large $n$ due to $O(n^{1.5})$ time complexity in naive implementations.

The Sieve of Eratosthenes, dating back to ancient Greece, solves this by systematically eliminating composites. It leverages the fact that every composite number has a prime factor $\leq \sqrt{n}$. Research shows variations improve efficiency, such as optimized memory access or pre-eliminating small primes like 2 and 3. This makes it ideal for finding all primes up to $n$, with proven time bounds like $O(n \log \log n)$.

Algorithm/Approach

Use the Sieve of Eratosthenes: Create a boolean array marking numbers from 2 to $n$ as potentially prime. Iteratively mark multiples of each prime starting from 2, skipping already-marked composites. Collect unmarked indices as primes. This batch-elimination approach avoids redundant checks, unlike per-number testing.

Step-by-Step Strategy

1. Initialize: Create a boolean list is_prime of length $n+1$, set all to True except indices 0 and 1 (False).
2. Handle 2 specially (optional optimization): Mark all even numbers >2 as False, then start sieving from 3 with step 2.
3. Sieving loop: For each $i$ from 2 to $\sqrt{n}$:

• If is_prime[i] is True, mark multiples $i^2, i^2 + i, \dots$ up to $n$ as False.

4. Collect results: Return list of $i$ where is_prime[i] is True, for $i \geq 2$.

Start marking multiples from $i^2$ (smaller multiples already handled).

Common Pitfalls

• Off-by-one errors: Array size must be $n+1$; forget to exclude 0/1 or include numbers >n.
• Inefficient marking: Starting multiples from $i$ (not $i^2$) or not using step $i$ wastes time; always start at $i^2$.
• Square root mishandling: Loop only to $\lfloor$\sqrt{n}$\rfloor$; use int(n**0.5) + 1 in Python.
• Even numbers: Not optimizing for 2 leads to unnecessary work; handle separately.
• Large n: Risk memory overflow; Python lists handle up to ~10^7 easily, but watch for $n=1$ or $n<2$ (return empty list).

Time & Space Complexity

• Time: $O(n \log \log n)$, as each composite is marked once per prime factor, with harmonic sum $\sum_{p \leq n} n/p \approx n \log \log n$.
• Space: $O(n)$ for the boolean array; optimizations like bit arrays reduce to $O(n/8)$.