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 880 / 935 800
Sieve of Eratosthenes 811 / 836 800
Segmented sieve 527 / 707 800
Prime factors 590 / 681 1000
Maximum GCD 513 / 583 1000
Divisors counting 515 / 551 1000
Largest common divisor 350 / 490 1100
Nearest Element 190 / 257 1200
Divisors counting 2 301 / 439 1200
GCD and LCM 292 / 302 1200
GGCD 236 / 245 1200
Square root sum 144 / 158 1200
Square number 273 / 384 1300
Sum sum sum 43 / 73 1500