Divisors of Natural Number and There Implementation In O(Sqrt(n)) Time Complexity

Divisors of natural number

 

If A and B are a non-zero integer of an integral domain then it is said that:
  • A divides B.
  • A is a divisor of B.
  • or, B is a multiple of A.
and, this is written as A/B if there exists an integer K, such that AK = B.

For Example, 8 is a divisor of 48 because 8 x 6 = 48, so it can be said that 48 is divisible by 8 or 48 is a multiple of 8.

Let us say that we are given a natural number N and we need to find it's all divisors.

For Example:
  • Divisors of 24 are 1, 2, 3, 4, 6, 8, 12, 24.
  • Divisors of 36 are 1, 2, 3, 4, 6, 9, 12, 18, 36.
So how we can find this?

Method - 1

  • The Brute Force approach.
Iterate a for loop from i = 1 to i = N and check the condition if N%i ==0 and if this is true then i is a divisor of N.
        
                   vector<int>vec(N);   // create a vector to store the divisors of N.
                   for ( int i = 1; i < =N; i++){    
                       if(N % i == 0)                  // check that N is divisible by i or not.
                           vec.push_back(i);        // if the condition is true then store i in the vector.
                   }
The time complexity for the above approach is O(N).

But the above approach can work for N upto 10^6, what if N is 10^12?

There is an efficient algorithm to find all the divisor in sqrt(N) time complexity. 

Claim:
  • Half of the divisors of N are less than Sqrt(N)         
For Example: 
                    Divisors of 24 are 1, 2, 3, 4, 6, 8, 12, 24, out of which 1, 2, 3, 4 are less than Sqrt(24)
                    Divisors of 15 are 1, 3, 5, 15, out of which 1, 3 are less than Sqrt(15).
All the divisors are present in pairs look at the example below.

                     Divisors of 24 are (1, 24), (2, 12), (3, 8), (4, 6)
                     Divisors of 36 are (1, 36), (2, 18), (3, 12), (6, 6)

If we multiply the elements of each pair the value would be N. We, however, have to care if N is a perfect square because in this case, we'll get two equal divisors.

Proof of correctness

Let us take two divisor d1 and d2 such that 1 ≤ d1 ≤ Sqrt(N) and Sqrt(N) ≤ d2 ≤ N. So minimum valued divisor = 1 and maximum valued divisor = N.
                                 
       1<= d1 <= sqrt(N)
Sqrt(N) <= d2 <= N
                    1
                    N
          …
           …
                                      
                 
 
           …
    
          …

           …
         
               Sqrt(N)

                  Sqrt(N)

Divisors of 24 are (1, 24), (2, 12), (3, 8), (4, 6)
Divisors of 36 are (1, 36), (2, 18), (3, 12), (4, 9), (6, 6)

In the above example, we can see that pairs are in the form of (d1, N/d1). It means d2 = N/d1 (N divided by d1).

For divisors of 24, we can also write (1, 24/1), (2, 24/2), (3, 24/3), (4, 24/4). and 4 is less than or equal to Sqrt(N).

For Divisors of 36, we can also write (1, 36/1), (2, 36/8), (3. 36/3), (4, 36/4), (6, 36/6), and 6 is equal to sqrt(N).

Here is the efficient algorithm to find all the divisors of a natural number in O(sqrt(N)) time complexity.

Iterate from i=1 to i<=sqrt(N) and if N%i == 0, then i and N/i both are divisors.

                   Vector<long int>divisors;
                   for(int i=1; i<=sqrt(N); i++)
                    {
                          if(N%i==0)
                           {
                                  divisors.push_back(i);
                                  divisors.push_back(N/i);
                            }
                     }



Written with 💗 by Manish

Comments