Number Theory Toolkit
A handful of classic routines cover most of it: sieve, Euclid, fast power and factorisation up to the square root.
Math & Number TheorySieve near linear, others logarithmicNew20 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
primes up to n
gcd or lcm
modular exponentiation
count factors
The template
Get this into muscle memory, then adapt the condition per problem.
const sieve = new Array(n + 1).fill(true); for (let i = 2; i * i <= n; i++) if (sieve[i]) for (let j = i * i; j <= n; j += i) sieve[j] = false;Watch Sieve of Eratosthenes
If you are stuck
The generic hint ladder for this pattern, in order.
- 1Trial division per number is wasteful when you need many answers.
- 2Mark multiples once, starting from the square.
- 3Only check divisors up to the square root.
Drill it
Every problem in the bank that uses this pattern.
0 / 20 solved