Sum of Divisors

Editorial

Sum of Divisors asks for the sum of all positive divisors of n — a number-theory problem whose key idea is to avoid a full O(n) scan.

Approach

Divisors come in pairs: if d divides n, so does n / d. Iterate only up to √n, adding both members of each pair — but count a repeated divisor once when d = n / d for a perfect square.

total = 0; d = 1
while d*d <= n:
    if n % d == 0:
        total += d
        if d != n // d:
            total += n // d
    d += 1
return total

Complexity

Time: O(√n). Space: O(1).