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 1686 / 1785 800
Sieve of Eratosthenes 1588 / 1654 800
Segmented sieve 1031 / 1321 800
Prime factors 1138 / 1273 1000
Maximum GCD 949 / 1067 1000
Divisors counting 990 / 1043 1000
Largest common divisor 676 / 891 1100
Nearest Element 396 / 487 1200
Divisors counting 2 588 / 802 1200
GCD and LCM 560 / 577 1200
GGCD 469 / 492 1200
Square root sum 413 / 440 1200
Square number 490 / 652 1300
Sum sum sum 167 / 215 1500