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 1031 / 1092 800
Sieve of Eratosthenes 958 / 987 800
Segmented sieve 616 / 817 800
Prime factors 696 / 798 1000
Maximum GCD 596 / 677 1000
Divisors counting 604 / 646 1000
Largest common divisor 419 / 567 1100
Nearest Element 235 / 307 1200
Divisors counting 2 363 / 517 1200
GCD and LCM 350 / 361 1200
GGCD 291 / 302 1200
Square root sum 207 / 222 1200
Square number 318 / 439 1300
Sum sum sum 75 / 107 1500