Stage 2 · Lesson 3 of 7
Primes and the sieve
A is a whole number above 1 whose only divisors are 1 and itself. To test one number, try divisors up to its square root. To find every prime up to n, use the of Eratosthenes: start with every number marked prime, and for each prime cross out its multiples.
It runs in O(n log log n), fast enough for n up to 10^7. A variation stores the smallest prime factor of every number, which lets you factorise any number up to n in O(log n). Use the sieve when a problem asks about primes for many numbers, and trial division for a few large ones.
Common trapsieving up to 10^9 because the values are that large, which needs far more memory than the limit.
A question to check yourself, an AI practice session and 1 cheat sheet entry come with the full roadmap. Unlock
Resources for this stage
Start with
- BookFreeCompetitive Programmer's Handbook
Antti Laaksonen · Beginner
Section 1.5 covers the maths basics and Chapter 21 covers number theory, from primes to modular inverses