Let integer n be factorized as
n = p_{1}^{e1} * p_{2}^{e2} * ... * p_{k}^{ek}
then the sum of divisors of n is represented as the following formula,
σ(n) = a_{1} * a_{2} * ... * a_{k}
where
a_{k} = | p_{k}^{ek+1} - 1 |
------------ | |
p_{k} - 1 |
Especially,
p_{k}^{ek+1} - 1 | = p_{k}^{ek} + ... + p_{k}^{2} + p_{k} + 1 |
------------ | |
p_{k} - 1 |
so if n=p^{e} then
σ(n) = p^{e} + ... + p^{2} + 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 = p_{1}^{e1} * p_{2}^{e2} * ... * p_{k}^{ek}
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 |
---|