Non-Performance Changes
Note that I haven't really made that many style or other recommendations as you didn't ask for any. However, I did still change two things. First, I avoided modifying an inputted variable, as this could have unintended consequences, and second I changed the name of divSum
to div_sum
.
Performance Changes
I noticed a couple of optimizations that you could make to your code to improve performance. The first change I made after noticing that there was a bit of unnecessary repetition in certain areas (Please forgive me for being slightly vague as it's currently 4 in the morning). Given any divisor of a number and that number itself, a second divisor can be calculated. I used this information to optimize the code to this form.
def proper_divisor_sum(N):
div_sum = [1] * (N+1)
div_sum[0], div_sum[1] = 0, 0
for i in range(2, int(math.sqrt(N))+1):
for j in range(i*i, N+1, i):
div_sum[j] += i + j//i if i != j//i else i
return div_sum
This code is roughly 33% faster than the original function. I originally thought that I needed to have an if-statement in there to handle perfect squares and the double-counting of those squares.
I then used this code to analyze the states of each individual iteration. This is what I found:
[[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 2, 0, 5, 0, 6, 0, 7, 0, 8, 0, 9, 0, 10, 0, 11, 0, 12],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 7, 0, 0, 8, 0, 0, 9, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 9]]
What I noticed was that the leading coefficients of each row progressed linearly, but the coefficients that followed obeyed a pattern. I'm sure you can work out the other patterns I saw in these numbers for yourself, but the primary thing this told me was that my previous assumption (about having to handle perfect squares) was actually a slip-up, as I had at some point forgotten that a number can't have more than one square, or I had at least accounted for the possibility in my code (Don't write code at 4 AM). Realizing this I was able to simplify the code down into its current form.
def proper_divisor_sum(N):
div_sum = [1] * (N+1)
div_sum[0], div_sum[1] = 0, 0
for i in range(2, int(math.sqrt(N))+1):
div_sum[i*i] += i
for j in range(i*i+i, N+1, i):
div_sum[j] += i + j//i
return div_sum
This final function is roughly 40% faster than your original function.