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 1425 / 1509 800
Sieve of Eratosthenes 1334 / 1386 800
Segmented sieve 856 / 1112 800
Prime factors 954 / 1072 1000
Maximum GCD 813 / 910 1000
Divisors counting 826 / 877 1000
Largest common divisor 569 / 764 1100
Nearest Element 326 / 409 1200
Divisors counting 2 503 / 682 1200
GCD and LCM 480 / 492 1200
GGCD 404 / 420 1200
Square root sum 335 / 356 1200
Square number 421 / 571 1300
Sum sum sum 141 / 180 1500