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 1405 / 1489 800
Sieve of Eratosthenes 1311 / 1364 800
Segmented sieve 840 / 1093 800
Prime factors 937 / 1053 1000
Maximum GCD 798 / 895 1000
Divisors counting 815 / 864 1000
Largest common divisor 560 / 751 1100
Nearest Element 320 / 403 1200
Divisors counting 2 490 / 669 1200
GCD and LCM 471 / 484 1200
GGCD 397 / 412 1200
Square root sum 324 / 345 1200
Square number 414 / 562 1300
Sum sum sum 137 / 176 1500