Numbers and recurrences
Fast algorithms for GCDs, primes and huge powers, then divide and conquer in general, with the master theorem for working out how fast a recursive method is.
About 6 hours of study
Learning objectives
- Compute a GCD and an LCM
- Find primes with a sieve
- Compute powers by repeated squaring
- Solve recurrences with the master theorem
Lessons
- 1
Number algorithms
Euclid's GCD, the sieve of Eratosthenes, and fast modular exponentiation: three old ideas used in every contest.
- 2
Divide and conquer and the master theorem Intermediate
Split a problem into smaller copies of itself, solve them recursively, combine the answers, and work out the running time with the master theorem.
Module practice
- GCD and LCMEasy
- Count the primesEasy
- Fast power modulo mMedium
- The modular inverseHard
- The largest number, by halvesEasy
- The best run of numbersMedium
- The closest pair of pointsHard