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 1324 / 1403 800
Sieve of Eratosthenes 1240 / 1286 800
Segmented sieve 794 / 1033 800
Prime factors 894 / 1004 1000
Maximum GCD 756 / 850 1000
Divisors counting 775 / 824 1000
Largest common divisor 535 / 713 1100
Nearest Element 306 / 386 1200
Divisors counting 2 469 / 644 1200
GCD and LCM 452 / 462 1200
GGCD 381 / 393 1200
Square root sum 302 / 322 1200
Square number 401 / 537 1300
Sum sum sum 130 / 166 1500