Sum of divisors: Difference between revisions
(→{{header|REXX}}: added the computer programming language REXX.) |
m (→{{header|REXX}}: changed a comment.) |
||
Line 63: | Line 63: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
<lang rexx>/*REXX program displays the first N sum of |
<lang rexx>/*REXX program displays the first N sum of divisors (shown in a columnar format). */ |
||
parse arg n . /*obtain optional argument from the CL.*/ |
parse arg n . /*obtain optional argument from the CL.*/ |
||
if n=='' | n=="," then n= 100 /*Not specified? Then use the default.*/ |
if n=='' | n=="," then n= 100 /*Not specified? Then use the default.*/ |
Revision as of 17:26, 20 December 2020
Given a positive integer, sum its positive divisors.
- Task
Show the result for the first 100 positive integers.
Python
Using prime factorization
<lang Python>def factorize(n):
assert(isinstance(n, int)) if n < 0: n = -n if n < 2: return k = 0 while 0 == n%2: k += 1 n //= 2 if 0 < k: yield (2,k) p = 3 while p*p <= n: k = 0 while 0 == n%p: k += 1 n //= p if 0 < k: yield (p,k) p += 2 if 1 < n: yield (n,1)
def sum_of_divisors(n):
assert(n != 0) ans = 1 for (p,k) in factorize(n): ans *= (pow(p,k+1) - 1)//(p-1) return ans
if __name__ == "__main__":
print([sum_of_divisors(n) for n in range(1,101)])</lang>
Finding divisors efficiently
<lang Python>def sum_of_divisors(n):
assert(isinstance(n, int) and 0 < n) ans, i, j = 0, 1, 1 while i*i <= n: if 0 == n%i: ans += i j = n//i if j != i: ans += j i += 1 return ans
if __name__ == "__main__":
print([sum_of_divisors(n) for n in range(1,101)])</lang>
- Output:
[1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, 42, 32, 36, 24, 60, 31, 42, 40, 56, 30, 72, 32, 63, 48, 54, 48, 91, 38, 60, 56, 90, 42, 96, 44, 84, 78, 72, 48, 124, 57, 93, 72, 98, 54, 120, 72, 120, 80, 90, 60, 168, 62, 96, 104, 127, 84, 144, 68, 126, 96, 144, 72, 195, 74, 114, 124, 140, 96, 168, 80, 186, 121, 126, 84, 224, 108, 132, 120, 180, 90, 234, 112, 168, 128, 144, 120, 252, 98, 171, 156, 217]
REXX
<lang rexx>/*REXX program displays the first N sum of divisors (shown in a columnar format). */ parse arg n . /*obtain optional argument from the CL.*/ if n== | n=="," then n= 100 /*Not specified? Then use the default.*/ say 'the sums of divisors for ' n " integers:"; say /*show what output is being shown*/ say '─index─' center(" sum of divisors ",70,'─') /*display a title for the tau numbers. */ w= max(7, length(n) ) /*W: used to align 1st output column. */ $= /*$: the output list, shown ten/line. */
do j=1 for N /*process N positive integers. */ $= $ || right( commas(sigma(j)), 7) /*add a sigma (sum) to the output list.*/ if j//10\==0 then iterate /*Not a multiple of 10? Don't display.*/ say right(commas(j-9), 6)' ' $ /*display partial list to the terminal.*/ $= /*start with a blank line for next line*/ end /*j*/
if $\== then say center((j-1) // 10, 7) $ /*any residuals sums left to display? */ exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ iSqrt: procedure; parse arg x; q= 1; r= 0; do while q<=x; q= q*4; end
do while q>1; q=q%4; _=x-r-q; r=r%2; if _>=0 then do;x=_;r=r+q; end; end; return r
/*──────────────────────────────────────────────────────────────────────────────────────*/ sigma: procedure; parse arg x; if x==1 then return 1; odd=x // 2 /* // ◄──remainder.*/
s= 1 + x /* [↓] only use EVEN or ODD integers.*/ do k=2+odd by 1+odd while k*k<x /*divide by all integers up to √x. */ if x//k==0 then s= s + k + x % k /*add the two divisors to (sigma) sum. */ end /*k*/ /* [↑] % is the REXX integer division*/ if k*k==x then return s + k /*Was X a square? If so, add √ x */ return s /*return (sigma) sum of the divisors. */</lang>
- output when using the default input:
the sums of divisors for 100 integers: ─index─ ────────────────────────── sum of divisors ─────────────────────────── 1 1 3 4 7 6 12 8 15 13 18 11 12 28 14 24 24 31 18 39 20 42 21 32 36 24 60 31 42 40 56 30 72 31 32 63 48 54 48 91 38 60 56 90 41 42 96 44 84 78 72 48 124 57 93 51 72 98 54 120 72 120 80 90 60 168 61 62 96 104 127 84 144 68 126 96 144 71 72 195 74 114 124 140 96 168 80 186 81 121 126 84 224 108 132 120 180 90 234 91 112 168 128 144 120 252 98 171 156 217