Is there a formula to calculate the sum of all proper divisors of a number?

I don’t need to list all proper divisors, I just want to get its sum. Because for a small number, checking all proper divisors and adding them up is not a big deal. However, for a large number, this would run extremely slow. Any idea?

Thanks,
Chan Nguyen

Answer

If the prime factorization of n is n=kpakk, where the pk are the distinct prime factors and the ak are the positive integer exponents, the sum of all the positive integer factors is k(aki=0pik).

For example, the sum of all of the factors of 120=2335 is (1+2+22+23)(1+3)(1+5)=1546=360.

For proper factors, subtract n from this sum. This may or may not be faster, depending on the number and how you’d get the prime factorization, but this is the typical technique for high school contest problems of this sort.

Attribution
Source : Link , Question Author : Chan , Answer Author : amWhy

Leave a Comment