Let integer n be factorized as
n = p1e1 * p2e2 * ... * pkek
then the sum of divisors of n is represented as the following formula,
σ(n) = a1 * a2 * ... * ak
where
ak = | pkek+1 - 1 |
------------ | |
pk - 1 |
Especially,
pkek+1 - 1 | = pkek + ... + pk2 + pk + 1 |
------------ | |
pk - 1 |
so if n=pe then
σ(n) = pe + ... + p2 + p + 1.
When we compute the sum of divisors during factorization of n,
this formula is more easy to handle. The algorithm is following,
w = w*p+1
n = n/p
The value of σ(n) where n = p1e1 * p2e2 * ... * pkek
is calculated by the following procedure.
s = s * w.
The program is following.
10 fnSigma(N) 20 local S,W,P 30 S=1 40 W=1:P=prmdiv(N) 50 if N@P=0 then W=W*P+1:N=N\P:goto 50 else S=S*W 60 if N>1 then 40 else return(S)
previous | index | next |
---|