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 823 / 873 800
Sieve of Eratosthenes 754 / 779 800
Segmented sieve 484 / 656 800
Prime factors 551 / 635 1000
Maximum GCD 478 / 542 1000
Divisors counting 474 / 507 1000
Largest common divisor 322 / 453 1100
Nearest Element 175 / 235 1200
Divisors counting 2 280 / 405 1200
GCD and LCM 265 / 275 1200
GGCD 215 / 225 1200
Square root sum 122 / 134 1200
Square number 253 / 354 1300
Sum sum sum 31 / 59 1500