Lesson 072
Primes & the Sieve
Primes · Trial Division · Sieve of Eratosthenes
1:00How to define and identify prime numbers, test primality with trial division, and find all primes up to n efficiently using the Sieve of Eratosthenes.
By the end, you can
- State the definition of a prime and explain why 0, 1, and 2 are special cases.
- Implement trial division for a single number and explain why it stops at sqrt(n).
- Trace the Sieve of Eratosthenes on a small grid, correctly applying both optimizations.
- Explain why the sieve starts each inner loop at i*i rather than 2*i.
- State the time complexity O(n log log n) and space complexity O(n) of the standard sieve.
- Describe what the segmented sieve does differently and why it reduces memory usage.
- Give at least two concrete applications of prime numbers in computer science.
Up next in Math, Memory & Files
