Module Basic number theory

Basic number theory

**Frequency: 7/10**

Resources

- [USACO Guide: Divisibility](https://usaco.guide/gold/divisibility?lang=cpp) - [CP Algorithms: Sieve of Eratosthenes](https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html)

Problems

Prime number 2 489 / 514 800
Sieve of Eratosthenes 450 / 469 800
Segmented sieve 316 / 384 800
Prime factors 325 / 372 1000
Maximum GCD 267 / 316 1000
Divisors counting 261 / 285 1000
Largest common divisor 178 / 247 1100
Nearest Element 92 / 121 1200
Divisors counting 2 151 / 241 1200
GCD and LCM 144 / 151 1200
GGCD 89 / 95 1200
Square number 145 / 192 1300