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 606 / 640 800
Sieve of Eratosthenes 559 / 581 800
Segmented sieve 311 / 474 800
Prime factors 397 / 461 1000
Maximum GCD 328 / 383 1000
Divisors counting 330 / 356 1000
Largest common divisor 218 / 310 1100
Nearest Element 117 / 152 1200
Divisors counting 2 191 / 288 1200
GCD and LCM 186 / 194 1200
GGCD 138 / 147 1200
Square number 190 / 263 1300