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 719 / 762 800
Sieve of Eratosthenes 664 / 685 800
Segmented sieve 395 / 563 800
Prime factors 468 / 540 1000
Maximum GCD 397 / 456 1000
Divisors counting 400 / 432 1000
Largest common divisor 271 / 376 1100
Nearest Element 144 / 199 1200
Divisors counting 2 231 / 345 1200
GCD and LCM 222 / 231 1200
GGCD 168 / 177 1200
Square root sum 77 / 87 1200
Square number 217 / 306 1300
Sum sum sum 14 / 33 1500