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 888 / 944 800
Sieve of Eratosthenes 817 / 842 800
Segmented sieve 530 / 712 800
Prime factors 593 / 686 1000
Maximum GCD 516 / 587 1000
Divisors counting 520 / 556 1000
Largest common divisor 352 / 491 1100
Nearest Element 192 / 259 1200
Divisors counting 2 303 / 442 1200
GCD and LCM 294 / 304 1200
GGCD 238 / 247 1200
Square root sum 145 / 159 1200
Square number 274 / 385 1300
Sum sum sum 45 / 75 1500