Bug: An elusive creature living in a program that makes it incorrect. The activity of "debugging", or removing bugs from a program, ends when people get tired of doing it, not when the bugs are removed.

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

classSumOfAllProperDivisors
{
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

classSumOfAllProperDivisors
{
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();
}
}

I'm working as Project Lead in Oracle. I'm mainly into Microsoft technologies but quite interested in Java and C. I'm not a professional blogger, whatever I find interesting I read it and write a blog post just to share my understanding.
View all posts by Sunil Kumar