I'm surprised this article doesn't optimize a little further. If you want to compute σ(n), and you can prime factor n, there's no need to go determining all th

I'm surprised this article doesn't optimize a little further. If you want to compute σ(n), and you can prime factor n, there's no need to go determining all the divisors of n and then adding them up. The σ function is multiplicative, i.e., one has σ(nm)=σ(n)σ(m) when (n,m)=1. So if you've factored n = p_1^a_1 * ... * p_k^a_k, it suffices to compute σ(p_i^a_i) for each i and then multiply them together. Meanwhile, while computing σ(p^a) can be done by summing, it can be done even more simply by noting that this is a geometric series and so sums to (p^(a+1)-1)/(p-1). Edit: Actually, not sure how this latter way compares to just doing Horner. Probably about the same, I imagine. I guess Horner would be the right way to do it if division is expensive for some reason.