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 1152 / 1216 800
Sieve of Eratosthenes 1075 / 1109 800
Segmented sieve 688 / 903 800
Prime factors 786 / 887 1000
Maximum GCD 661 / 748 1000
Divisors counting 682 / 729 1000
Largest common divisor 473 / 635 1100
Nearest Element 269 / 343 1200
Divisors counting 2 407 / 571 1200
GCD and LCM 399 / 409 1200
GGCD 333 / 344 1200
Square root sum 257 / 274 1200
Square number 356 / 486 1300
Sum sum sum 104 / 139 1500