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 1017 / 1078 800
Sieve of Eratosthenes 943 / 972 800
Segmented sieve 597 / 799 800
Prime factors 675 / 779 1000
Maximum GCD 581 / 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 71 / 100 1500