Sum of All Divisors of a Number
Last Updated: June 7, 2026
Understanding the Problem
Find every number that divides n evenly and add them together. A number i is a divisor of n when n % i equals 0. The list always starts at 1, because 1 divides every integer, and ends at n, because every number divides itself.
Take n = 12. From 1 to 12, the values that divide it cleanly are 1, 2, 3, 4, 6, 12, which sum to 28. The rest, like 5, 7, and 8, leave a remainder and are skipped.
The challenge is finding all the divisors efficiently. The direct method tests every candidate up to n, which is fine for small inputs. With n as large as 10^6, a faster method uses the fact that divisors come in pairs.
Key Constraints:
ncan be as large as10^6→ A linear scan does up to a million checks, which is acceptable, but a square-root scan does only about a thousand and scales far better.- The sum can exceed a small integer → Accumulate the total in a 64-bit type so the value has room to grow as inputs get larger.
nis always positive → There are no negative or zero edge cases to guard against, so the loop logic stays simple.
Approach 1: Linear Scan
Intuition
Walk through every candidate from 1 to n, test each one with the modulo operator, and add the ones where n % i is 0. This is easy to reason about and a solid baseline before optimizing.
Algorithm
- Initialize an accumulator
sumto0. - Loop
ifrom1ton. - If
n % iequals0, theniis a divisor, so additosum. - After the loop ends, return
sum.
Example Walkthrough
Input:
Walking from 1 to 12, the values where 12 % i equals 0 are 1, 2, 3, 4, 6, 12. Each one gets added to the running total: 1 + 2 + 3 + 4 + 6 + 12. The numbers 5, 7, 8, 9, 10, 11 all leave a remainder, so they are skipped. The final sum is 28.
Code
- Time Complexity: O(n). The loop runs once for each value from
1ton, performing one modulo check each time. - Space Complexity: O(1). Only the running sum is stored, regardless of how large
nis.
Approach 2: Scan to Square Root
Intuition
Divisors come in pairs. If i divides n, then n / i divides n too. For n = 12, 2 pairs with 6, and 3 pairs with 4. One member of each pair is at most the square root of n and the other is at least the square root, so scanning only up to the square root finds both members of every pair.
Loop i while i * i <= n. Whenever i divides n, add both i and its partner n / i. One detail needs care: when n is a perfect square, i equals n / i at the middle, so add that divisor only once to avoid counting it twice.
Algorithm
- Initialize an accumulator
sumto0. - Loop
istarting at1whilei * i <= n. - If
n % iequals0, theniis a divisor: - Add
itosum. - Compute the partner
n / i. If it differs fromi, add it tosumas well. If it equalsi, skip it so the perfect-square divisor is not double counted. - After the loop ends, return
sum.
Example Walkthrough
Input:
The loop runs while i * i <= 12, so i goes 1, 2, 3 (since 4 * 4 = 16 exceeds 12). At i = 1, 1 divides 12, so add the pair 1 + 12. At i = 2, 2 divides 12, so add the pair 2 + 6. At i = 3, 3 divides 12, so add the pair 3 + 4. The collected pairs are 1+12, 2+6, 3+4, and together they sum to 28. Because 12 is not a perfect square, every pair has two distinct members, so no value is skipped.
Code
- Time Complexity: O(sqrt n). The loop stops once
ipasses the square root ofn, so it runs about sqrt(n) times instead ofntimes. - Space Complexity: O(1). The running sum and a single pair variable are the only storage used.