Find the Sum of Divisors of a Number

Finding the sum of divisors of a number is a fundamental problem in number theory with applications in various areas of computer science and mathematics. This post will look at different approaches to solving this problem in Python, ranging from simple brute-force methods to more efficient algorithms. We’ll examine the code, explain the logic, and analyze the time complexity of each approach.

Method 1: Brute-Force Approach

The most straightforward method involves iterating through all numbers from 1 up to the given number (n) and checking if each number is a divisor. If it is, we add it to the sum.

def sum_divisors_bruteforce(n):
  """
  Calculates the sum of divisors of a number using a brute-force approach.

  Args:
    n: The input number (integer).

  Returns:
    The sum of divisors of n.  Returns 0 if n is less than 1.
  """
  if n < 1:
    return 0
  total = 0
  for i in range(1, n + 1):
    if n % i == 0:
      total += i
  return total

# Example usage
number = 12
sum_of_divisors = sum_divisors_bruteforce(number)
print(f"The sum of divisors of {number} is: {sum_of_divisors}") # Output: 28

This approach has a time complexity of O(n), which means the execution time grows linearly with the input number. For large numbers, this can become quite slow.

Method 2: Optimized Approach using the Square Root

We can optimize the brute-force approach by only iterating up to the square root of n. For every divisor i found below the square root, there’s a corresponding divisor n/i above the square root.

import math

def sum_divisors_optimized(n):
  """
  Calculates the sum of divisors of a number using an optimized approach.

  Args:
    n: The input number (integer).

  Returns:
    The sum of divisors of n. Returns 0 if n is less than 1.
  """
  if n < 1:
    return 0
  total = 0
  for i in range(1, int(math.sqrt(n)) + 1):
    if n % i == 0:
      total += i
      if i * i != n:  # Avoid double-counting perfect squares
        total += n // i
  return total

# Example usage
number = 12
sum_of_divisors = sum_divisors_optimized(number)
print(f"The sum of divisors of {number} is: {sum_of_divisors}") # Output: 28

This optimized version has a time complexity of O(√n), a significant improvement over the brute-force method.

Method 3: Using Prime Factorization (Advanced)

For even greater efficiency, especially with very large numbers, prime factorization can be employed. This method involves finding the prime factors of the number and using their exponents to calculate the sum of divisors. However, this approach requires a separate algorithm for prime factorization, which can be computationally intensive for extremely large numbers. We won’t look at the implementation details here as it’s beyond the scope of this introductory post, but it’s worth noting as a highly efficient solution for advanced scenarios.