Prime Finder

mediumFREEControl FlowPython AlgorithmsPython Foundations

Problem Statement

Find all prime numbers up to a given limit.

Background

A prime number is only divisible by 1 and itself. The Sieve of Eratosthenes is an efficient algorithm:

Create a list of numbers from 2 to n
Start with the first prime (2)
Remove all multiples of that prime
Move to the next unmarked number
Repeat until done

Your Task

Write a function find_primes(n) that returns all prime numbers up to n.

Output Format

Return a list of prime numbers in ascending order.

Example

Input

n = 20

Output

[2, 3, 5, 7, 11, 13, 17, 19]

Reasoning

Input: n = 20 is an inclusive upper limit, so the candidates are the 19 whole numbers $2, 3, \dots, 20$ (1 is not prime by definition).
A number is composite exactly when it has a prime factor smaller than itself. If $m = a \cdot b$ with $a \le b$ , then $a^2 \le m \le 20$ , so $a \le \sqrt{20} \approx 4.47$ . Every composite up to 20 is therefore divisible by 2 or 3.
Multiples of 2 (other than 2 itself): $4, 6, 8, 10, 12, 14, 16, 18, 20$ , which is 9 composites.
Multiples of 3 not already listed: $9 = 3^2$ and $15 = 3 \cdot 5$ , which is 2 more. Note that $6, 12, 18$ were already counted.
That leaves $19 - 11 = 8$ survivors: [2, 3, 5, 7, 11, 13, 17, 19].
Output: a list of integers in ascending order. Notice that the limit is inclusive: with n = 19, 19 would still appear, and with n = 2 the answer is [2].

Constraints

n >= 2
Use an efficient approach for larger n

Learn this in

Python FoundationsFoundations

More from Python Foundations

Magic Methodsmedium Inheritance and Polymorphismmedium Basic Class Creationeasy Decorator Implementationmedium Higher-Order Functionsmedium

Concept primer

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

Initialize: Create a boolean list is_prime of length $n+1$ , set all to True except indices 0 and 1 (False).
Handle 2 specially (optional optimization): Mark all even numbers >2 as False, then start sieving from 3 with step 2.
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.

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)$ .

Aspect	Complexity	Notes
Time	O(n log log n)	Optimal for dense prime lists
Space	O(n)	Linear in input size

solution.py

Python 3.13

Test results