Number Theory Meet 2

Topics

1. Integer factorization
   • O(n)
   • O($\sqrt{n}$ )

2. Primality Testing
   • O($\sqrt{n}$ )

3. Sieve Algorithm

4. Linear Sieve

5. Applications of Sieve
   • checking prime in O(1)
   • factorize in O(logN)
   • Sum/Num divisors
   • highest/smallest prime divisor
   • euler totient function
   • Segmented Sieve

6. Totient Function and Applications

7. Miller Rabin

Questions

1. https://codeforces.com/problemset/problem/26/A (Almost prime, easy)

2. https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3651 (medium)

3. https://codeforces.com/contest/653/problem/G (all maths requires a bit of sieve, hard)