Number Theory - Primality Test
1. Naive Approach (Brute Force):
As you may have predicted this is a brute force approach so we will be checking for every possible case.
Basically, we will be iterating from 2 to n-1 and for every number we will check if it divides ‘n’. And if we find any such number then our number is not prime else our number is prime.
Below is the implementation of naïve approach:
2. Optimized Approach – O( sqrt(n) ):
· To optimize naïve method, we have to observe a wonderful relation between the number that we are checking (i.e. from 2 to n-1)
· All divisors of a number ‘N’ occur in pair of (a,b) such that a * b = N
· For E.g. 12 has following divisors:
D = 1,2,3,4,5,6,12 here pairs are (1,12) , (2,6) , (3,4) hence we only need
to run our loop till sqrt(N) i.e. sqrt(12) = 3(approx)
· Voila !! we optimized our naïve approach by simple observation of number theory.
Below is the implementation of optimized approach:
Time Complexity: O( sqrt(n) )
3. Sieve of Erastosthenes – O(1):
- Why we need sieve ?
Suppose we need to answer ‘Q’ queries Q <= a million
Input: N
Consider N <= 10^6
Output: prime or not
Now here we cannot use O( sqrt(n) ) approach because as discussed in our previous articles of time complexity analysis this approach will not work in given time constraint and will definitely lead to Time Limit Exceeded (TLE) verdict which certainly indicates we need to answer queries more efficiently probably in O(logn) or O(1).
- How sieve works ?
Step1 : The algorithm is simple we just make an array of size 10^6 initialize it with 1(indicating prime) except for ‘0’ and ‘1’ position which is initialized as ‘0’.
Step2 : Now we run a loop from 2 to sqrt(10^6) and if current element value is ‘1’ in array then we run a loop inside from i * i to 10^6 and initialize all of its multiple with ‘0’ (indicating not prime).
Step3 : Finally we are left with an array which have ‘1’(indicating prime) and ‘0’ (indicating not prime) and now we can tell whether a given number is prime or not in O(1) voila !!
Still not much clear don’t worry we will make it crystal clear as we are known for it 😊.
Have a look at below video and try to connect it with the steps given above.
As you can observe in above video we are starting from 2(considering it as prime) and colouring all of its multiples.
then selecting next uncoloured box and doing the same process till sqrt(n) in our case sqrt(120) = 10(approx).
Finally we are left with all primes as in purple in above video and also the number which we selected first as uncoloured.
Below is the implementation of sieve of eratosthenes:
Pre-processing Time Complexity: O( NLog(LogN) )
Answering Query : O(1)
Extra Space : O(N)
Note : The pre-processing time is more for sieve of erastothenes but this makes us answer query in constant time, and this is why sieve is much important in number theory for finding primes.
It is always better to solve a question after you learn a new concept as it helps in making concrete concepts.
So, below are problems which are handpicked by Programmers Army to make your concept more solid which you learned.
2. Problem from hackerearth: https://www.hackerearth.com/practice /math/number-theory/primality-tests/practice-problems/algorithm/micro-and-prime-prime-1/
We highly recommend to solve above problems if you got stuck read editorials for guidance.
So that’s it for this article we will be coming up with our next article on further topics of number theory very soon till then keep learning, keep coding, keep reading and keep improving !!
Happy Coding 😊
By Programmers Army