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 1014 / 1075 800
Sieve of Eratosthenes 940 / 969 800
Segmented sieve 597 / 797 800
Prime factors 673 / 777 1000
Maximum GCD 580 / 658 1000
Divisors counting 592 / 633 1000
Largest common divisor 403 / 552 1100
Nearest Element 225 / 294 1200
Divisors counting 2 351 / 502 1200
GCD and LCM 338 / 349 1200
GGCD 279 / 290 1200
Square root sum 193 / 207 1200
Square number 305 / 426 1300
Sum sum sum 70 / 99 1500