Number Theory for Coding Newbies
If you don’t want to stick your head in the sand to avoid embarrassing situations as above,it is recommended to read further.
Here is me, Samarth Mittal presenting before you my first blog on Competitive Programming. It has been almost a year since I have been participating in this amazing sport called Competitive Programming.
Starting as a beginner, I faced a lot of problems which I do not want others, especially the newbies to face as they move forward in their journey through competitive coding.
In this blog I would like to explore some basic concepts of Number Theory, often used in Competitive Coding questions.
Number Theory is one of the most important topics in Mathematics and is vital to understand.
Getting Started, some quick to discuss and important topics of Number Theory are Prime Numbers using Sieve of Eratosthenes and Euler Totient Function.
You might be asked whether or not a number is prime or not. Well, the naive approach is to run a loop from 1 to n and count the number of divisors of n in this range. If the number of divisors is equal to 2, then the number is prime. This approach takes O(n) time. A better approach would be to run the loop from 1 to √n and count the divisors. This approach works since if there is a divisor d of n greater than √n, then there would be another divisor (n/d) of n, lesser than √n. This reduces the time complexity to O(√n).
But, what if you can find all prime numbers till n in O(n log log n)time complexity ?
Sounds Interesting!!!
Here comes the Sieve of Eratosthenes. In this method, in an operation a prime number is picked and all its multiples are marked. After all such operations are completed, all the unmarked numbers that remain are prime.
The idea behind is this: A number is prime, if none of the smaller prime numbers divides it. Since we iterate over the prime numbers in order, we already marked all numbers, who are divisible by at least one of the prime numbers, as divisible. Hence if we reach a cell and it is not marked, then it isn’t divisible by any smaller prime number and therefore has to be prime.
- Implementation -
Here is a nice animation to visualize how the algorithm works:
Using this kind of implementation the algorithm consumes O(n) memory. This might pose a problem for numbers greater than 10⁸ or so since the memory overflow will take place.
For that Segmented Sieve is used, which I will not discuss here.It can be read from here:
- Some practice problems on Sieve of Eratosthenes:
Bonus Gyaan:
Goldbach conjecture- It states that every even integer greater than 2 can be expressed as the sum of two primes. Try:
Next, I would be discussing Euler Totient Function (ETF), also known as phi-function, which counts the number of integers between 1 and N inclusive, which are coprime to N. Two numbers are coprime if their greatest common divisor(gcd) is 1.
For example;
ϕ(10)=4, (ie. 1,3,7,9)
ϕ(11)=10 (ie. 1,2,3,4,5,6,7,8,9,10).
Some Properties of ETF -
- The sum of all values of Totient Function of all divisors of N is equal to N.
- ETF for a prime number P is equal to P-1 as the number have a GCD of 1 with all numbers less than or equal to it except itself. Eg. Φ(11)=10 .
- For two co-prime numbers A and B, Φ(A . B)= Φ(A) . Φ(B)
Implementation -
This implementation has a time complexity of O(√n).
- Some practice problems on Euler Totient Function :
For all the math-enthusiasts, you can always visit Project Euler, a website designed for questions related to Mathematics at its best.
Now, I would like to take leave and let you wander through the endless ecstasies you will experience as you continue doing Competitive Programming.
Happy Coding!!
