# 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)
{
int sum = 0;
for (int i = 1; i <= num/2; ++i)
{
if (num % i == 0)
{
sum += i;
}
}
Console.WriteLine(\$"Divisor sum: {sum}");
}
}```

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 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}");