We are back with the new article on introduction to number theory (The most demanded and hot topic in the world of Algorithms).
If you are a person who loves mathematics then you will fall in love with number theory, and if you don’t love mathematics, we will make number theory fall in love with you 😊.
Be relaxed and keep reading.
In this article we shall look at some extra-ordinary introduction to Number Theory basics, partly because they are interesting in themselves, certainly because they are used a lot in Competitive Programming, and partly because they will give you a flavour of what Number Theory is about.
Believe me if you are not good at number theory than you will probably be not able to perform good in coding contest as some coding contest are specifically focussed on Number Theory concepts.
1. What is Number Theory?
Topics covered in number theory articles on Programmers Army:
1. Primality Test:
a. Naive Approach (Brute Force).
b. Optimized Approach ( O(sqrt(n) ).
c. Sieve of Eratosthenes. ( O(1) ).
2. Prime Factorization:
a. Naive Approach (Brute Force).
b. Optimized Approach ( O(sqrt(n) ).
c. Prime factorization using sieve ( O(logn) ).
3. Binary Exponentiation (Technique to calculate a^n in O(logn) ).
4. Matrix Exponentiation.
5. Calculate ‘Nth’ element of recurrence relation in O(logn)
6. G.C.D algorithm:
a. Naive Approach (Brute Force).
b. Euclid Division Algorithm ( O(logn) ).
7. Modular Arithmetic – Part 1 (Basics)
8. Modular Arithmetic – Part 2:
a. Modular Exponentiation.
b. Modulo multiplicative inverse:
i. Fermat’s little theorem,
ii. Extended Euclidean Algorithm.
9. Total Divisors from prime factorization.
10. Binomial co-efficient using modulo inverse.
11. Euler’s Totient Function.
a. Naive Approach.
b. Optimized Approach.
12. Calculating Euler’s Phi function using sieve ( O(Nlog(logN)) ).
13. Euler’s Totient function & G.C.D sum.
14. And Many More…
These were very detailed glimpse of topics which we are going to cover in this series of number theory articles, So even if you are familiar with some concepts mentioned above we will make that understanding crystal-clear in your mind with our best efforts, and if you are a newbie in number theory than reading this articles in above mentioned sequence will make you pro in Number Theory.
So that’s it for this article as this is just introduction of number theory we will be coming up with our next article very soon till then keep learning, keep coding, keep reading and keep improving !!
Happy Coding 😊
By Programmers Army