Sum of all proper divisors of a natural number in O(n)

Suppose you have a natural number say 20, you need to find out sum of its divisors. How will you start?

Input: number = 20

Output: 22

As we all know that a proper divisor can’t be greater than number/2. Also a prime divisor can’t be greater than Squar Root of the number. So now we have two approaches to compute above sum:

Method1 – Logic is, a proper divisor can’t be greater than number/2. This logic is preety simple but you have to loop till number/2. So suppose number is 100, then we have to iterate 50 times. Time complexity is O(n).

Step1: Loop till condition i <= number/2 is true.
Step2: Check foe proper divisors
Step3: Sum all the proper divisor.

Input: 20
Output: 1 + 2 + 4 + 5 + 10 = 22

class SumOfAllProperDivisors
 {
       static void Main(string[] args)
       {
             Console.Write("Please enter a number: ");
             int num = Convert.ToInt32(Console.ReadLine());
             int sum = 0;
             for (int i = 1; i <= num/2; ++i)
             {
                    if (num % i == 0)
                    {
                          sum += i;
                    }
            }
            Console.WriteLine($"Divisor sum: {sum}");
            Console.ReadKey();
      }
 }

Method2 – Logic is, a prime divisor can’t be greater than Squar Root of the number. In this case our loop iteration will be considerabily less in compare to Method1. Time complexity is O(n).

Step1: Loop till condition i <= Squar root of number is true.
Step2: Check for proper divisor.
Step3: if it is proper divisor then add this number to our result.
Step3.1: Check for the Quotient, if it is not same as divisor and divisor is not equal to 1 then add quotient to our result.

Input: 20
Output: 1 + (2 + 10) + (4 + 5) = 22

class SumOfAllProperDivisors
 {
     static void Main(string[] args)
     {
           Console.Write("Please enter a number : ");
           int num = Convert.ToInt32(Console.ReadLine());
           int sum = 0;
           for (int i = 1; i <= Math.Sqrt(num); ++i)
           {
                  if (num % i == 0)
                  {
                        sum += i;
                        if ((num / i != i) && i != 1)
                        {
                               sum += (num / i);
                        }
                   }
            }
            Console.WriteLine($"Divisor sum: {sum}");
            Console.ReadKey();
     }
 }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s