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 1318 / 1396 800
Sieve of Eratosthenes 1235 / 1280 800
Segmented sieve 793 / 1032 800
Prime factors 894 / 1002 1000
Maximum GCD 755 / 848 1000
Divisors counting 773 / 822 1000
Largest common divisor 535 / 711 1100
Nearest Element 306 / 386 1200
Divisors counting 2 468 / 644 1200
GCD and LCM 452 / 462 1200
GGCD 380 / 392 1200
Square root sum 302 / 322 1200
Square number 401 / 537 1300
Sum sum sum 129 / 165 1500