Proper divisors: Difference between revisions

Content added Content deleted
m (→‎{{header|REXX}}: added/changed comments and whitespace, used a template for the OUTPUTs, simplified the code, used better idiomatic code for handling C.L. input, cre-worked the integer square root code.)
Line 3,297: Line 3,297:
With the (subroutine) optimization, it's over twenty times faster.
With the (subroutine) optimization, it's over twenty times faster.
<lang rexx>/*REXX program finds proper divisors (and count) of integer ranges; finds the max count.*/
<lang rexx>/*REXX program finds proper divisors (and count) of integer ranges; finds the max count.*/
parse arg bot top inc range xtra /*get optional arguments from CL.*/
parse arg bot top inc range xtra /*obtain optional arguments from the CL*/
top=word(top bot 10,1); bot=word(bot 1,1); inc=word(inc 1,1) /*first range.*/
if bot=='' | bot=="," then bot= 1 /*Not specified? Then use the default.*/
if range=='' then range=top /*use TOP for the 2nd range. */
if top=='' | top=="," then top= 10 /* " " " " " " */
w=length(top)+1; numeric digits max(9,w) /*'nuff digits for // operation*/
if inc=='' | inc=="," then inc= 1 /* " " " " " " */
if range=='' | range=="," then range=20000 /* " " " " " " */
m=0
w=1+max(length(top), length(bot), length(range)) /*determine the biggest number of these*/
do n=bot to top by inc; q=Pdivs(n); #=words(q); if q=='∞' then #=q
numeric digits max(9, w) /*have enough digits for // operator.*/
⚫
say right(n,max(20,digits())) 'has' center(#,4) "proper divisors: " q
end /*n*/ /* [↑] process 1st range of integers.*/
@.= 'and' /*a literal used to separate #s in list*/
say; @.= 'and'
do n=bot to top by inc /*process the first range specified. */
do r=1 for range; q=Pdivs(r); #=words(q); if #<m then iterate
q=Pdivs(n); #=words(q) /*get proper divs; get number of Pdivs.*/
if q=='∞' then #=q /*adjust number of Pdivisors for zero. */
@.#=@.# @. r; m=#
⚫
say right(n, max(20, w) ) 'has' center(#, 4) "proper divisors: " q
⚫
end /*r*/ /* [↑] process 2nd range of integers.*/
end /*n*/
⚫
__= 'is the highest number of proper divisors in range 1──►'range
say /* [↑] process 1st range of integers.*/
⚫
say m __", and it's for: " subword(@.m,3)
m=0 /*M ≡ maximum number of Pdivs (so far).*/
do r=1 for range /*process the second range specified. */
q=Pdivs(r); #=words(q) /*get proper divs; get number of Pdivs.*/
if #<m then iterate /*Less then max? Then ignore this #. */
@.#=@.# @. r; m=# /*add this Pdiv to max list; set new M.*/
⚫
end /*r*/ /* [↑] process 2nd range of integers.*/

⚫
say m ' is the highest number of proper divisors in range 1──►'range,
⚫
", and it's for: " subword(@.m, 3)
say /* [↓] handle any given extra numbers.*/
say /* [↓] handle any given extra numbers.*/
do i=1 for words(xtra); n=word(xtra,i)
do i=1 for words(xtra); n=word(xtra, i) /*obtain an extra number from XTRA list*/
numeric digits max(9,length(n)+1); q=Pdivs(n); #=words(q)
w=max(w, 1 + length(n) ) /*use maximum width for aligned output.*/
say right(n,max(20,w)) 'has' center(#,4) "proper divisors."
numeric digits max(9, 1 + length(n) ) /*have enough digits for // operator.*/
end /*i*/ /* [↑] support extra specified integers*/
q=Pdivs(n); #=words(q) /*get proper divs; get number of Pdivs.*/
⚫
say right(n, max(20, w) ) 'has' center(#, 4) "proper divisors."
⚫
end /*i*/ /* [↑] support extra specified integers*/
exit /*stick a fork in it, we're all done. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
Pdivs: procedure; parse arg x,b; x=abs(x); if x==1 then return ''
Pdivs: procedure; parse arg x,b; x=abs(x); if x==1 then return '' /*unity?*/
odd=x//2; if x==0 then return '∞'
odd=x // 2; if x==0 then return '∞' /*zero ?*/
r=0 /* [↓] ══integer square root══ ___ */
q=1; do while q<=z; q=q*4; end /*R: an integer which will be √ X */
do while q>1; q=q%4; _=z-r-q; r=r%2; if _>=0 then do; z=_; r=r+q; end
end /*while q>1*/ /* [↑] compute the integer sqrt of X.*/
a=1 /* [↓] use all, or only odd #s. ___*/
a=1 /* [↓] use all, or only odd #s. ___*/
do j=2+odd by 1+odd while j*j<x /*divide by some integers up to √ X */
do j=2 +odd by 1 +odd to r -(r*r==x) /*divide by some integers up to √ X */
if x//j==0 then do; a=a j; b=x%j b /*if ÷, add both divisors to α & ß. */
if x//j==0 then do; a=a j; b=x%j b /*if ÷, add both divisors to α & ß. */
end
end
Line 3,328: Line 3,343:
if j*j==x then return a j b /*Was X a square? If so, add √ X */
if j*j==x then return a j b /*Was X a square? If so, add √ X */
return a b /*return the divisors (both lists). */</lang>
return a b /*return the divisors (both lists). */</lang>
'''output''' &nbsp; when using the following input: &nbsp; <tt> 0 &nbsp; 10 &nbsp; 1 &nbsp; &nbsp; &nbsp; 20000 &nbsp; &nbsp; &nbsp; 166320 &nbsp; 1441440 &nbsp; 11796480000 </tt>
{{out|output|text=&nbsp; when using the following input: &nbsp; <tt> 0 &nbsp; 10 &nbsp; 1 &nbsp; &nbsp; &nbsp; 20000 &nbsp; &nbsp; &nbsp; 166320 &nbsp; 1441440 &nbsp; 11796480000 </tt>}}
<pre>
<pre>
0 has ∞ proper divisors: ∞
0 has ∞ proper divisors: ∞
Line 3,355: Line 3,370:
It accomplishes a faster speed by incorporating the calculation of an &nbsp; ''integer square root'' &nbsp; of an integer &nbsp; (without using any floating point arithmetic).
It accomplishes a faster speed by incorporating the calculation of an &nbsp; ''integer square root'' &nbsp; of an integer &nbsp; (without using any floating point arithmetic).
<lang rexx>/*REXX program finds proper divisors (and count) of integer ranges; finds the max count.*/
<lang rexx>/*REXX program finds proper divisors (and count) of integer ranges; finds the max count.*/
parse arg bot top inc range xtra /*get optional arguments from CL.*/
parse arg bot top inc range xtra /*obtain optional arguments from the CL*/
top=word(top bot 10,1); bot=word(bot 1,1); inc=word(inc 1,1) /*first range.*/
if bot=='' | bot=="," then bot= 1 /*Not specified? Then use the default.*/
if range=='' then range=top /*use TOP for the 2nd range. */
if top=='' | top=="," then top= 10 /* " " " " " " */
w=length(top)+1; numeric digits max(9,w) /*'nuff digits for // operation*/
if inc=='' | inc=="," then inc= 1 /* " " " " " " */
if range=='' | range=="," then range=20000 /* " " " " " " */
m=0
w=1+max(length(top), length(bot), length(range)) /*determine the biggest number of these*/
do n=bot to top by inc; q=Pdivs(n); #=words(q); if q=='∞' then #=q
numeric digits max(9, w) /*have enough digits for // operator.*/
⚫
say right(n,max(20,digits())) 'has' center(#,4) "proper divisors: " q
end /*n*/ /* [↑] process 1st range of integers.*/
@.= 'and' /*a literal used to separate #s in list*/
say; @.='and'
do n=bot to top by inc /*process the first range specified. */
do r=1 for range; q=Pdivs(r); #=words(q); if #<m then iterate
q=Pdivs(n); #=words(q) /*get proper divs; get number of Pdivs.*/
if q=='∞' then #=q /*adjust number of Pdivisors for zero. */
@.#=@.# @. r; m=#
say right(n, max(20, w) ) 'has' center(#, 4) "proper divisors: " q
⚫
end /*r*/ /* [↑] process 2nd range of integers.*/
end /*n*/
⚫
__= 'is the highest number of proper divisors in range 1──►'range
say /* [↑] process 1st range of integers.*/
⚫
say m __", and it's for: " subword(@.m,3)
m=0 /*M ≡ maximum number of Pdivs (so far).*/
do r=1 for range /*process the second range specified. */
q=Pdivs(r); #=words(q) /*get proper divs; get number of Pdivs.*/
if #<m then iterate /*Less then max? Then ignore this #. */
@.#=@.# @. r; m=# /*add this Pdiv to max list; set new M.*/
end /*r*/ /* [↑] process 2nd range of integers.*/

⚫
say m ' is the highest number of proper divisors in range 1──►'range,
⚫
", and it's for: " subword(@.m, 3)
say /* [↓] handle any given extra numbers.*/
say /* [↓] handle any given extra numbers.*/
do i=1 for words(xtra); n=word(xtra,i)
do i=1 for words(xtra); n=word(xtra, i) /*obtain an extra number from XTRA list*/
numeric digits max(9,length(n)+1); q=Pdivs(n); #=words(q)
w=max(w, 1 + length(n) ) /*use maximum width for aligned output.*/
say right(n,max(20,w)) 'has' center(#,4) "proper divisors."
numeric digits max(9, 1 + length(n) ) /*have enough digits for // operator.*/
end /*i*/ /* [↑] support extra specified integers*/
q=Pdivs(n); #=words(q) /*get proper divs; get number of Pdivs.*/
say right(n, max(20, w) ) 'has' center(#, 4) "proper divisors."
end /*i*/ /* [↑] support extra specified integers*/
exit /*stick a fork in it, we're all done. */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
Pdivs: procedure; parse arg x,b; x=abs(x); if x==1 then return ''
Pdivs: procedure; parse arg x,b; x=abs(x); if x==1 then return '' /*unity?*/
odd1=x//2 + 1; if x==0 then return '∞' /* ___*/
odd=x // 2; if x==0 then return '∞' /*zero ?*/
z=x; r=0; q=1; do while q<=z; q=q*4; end /*R: an integer which will be √ X */
r=0 /* [↓] ══integer square root══ ___ */
do while q>1; q=q%4; _=z-r-q; r=r%2; if _>=0 then do; z=_; r=r+q; end; end
q=1; do while q<=z; q=q*4; end /*R: an integer which will be √ X */
do while q>1; q=q%4; _=z-r-q; r=r%2; if _>=0 then do; z=_; r=r+q; end
end /*while q>1*/ /* [↑] compute the integer sqrt of X.*/
a=1 /* [↓] use all, or only odd #s. ___*/
a=1 /* [↓] use all, or only odd #s. ___*/
do j=1+odd1 by odd1 to r - (r*r==x) /*divide by some integers up to √ X */
do j=2 +odd by 1 +odd to r -(r*r==x) /*divide by some integers up to √ X */
if x//j==0 then do; a=a j; b=x%j b /*if ÷, add both divisors to α & ß. */
if x//j==0 then do; a=a j; b=x%j b /*if ÷, add both divisors to α & ß. */
end
end
Line 3,388: Line 3,416:
if j*j==x then return a j b /*Was X a square? If so, add √ X */
if j*j==x then return a j b /*Was X a square? If so, add √ X */
return a b /*return the divisors (both lists). */</lang>
return a b /*return the divisors (both lists). */</lang>
'''output''' &nbsp; is identical to the 2<sup>nd</sup> REXX version. <br><br>
{{out|output|text=&nbsp; is identical to the 2<sup>nd</sup> REXX version when using the same inputs.}} <br><br>


=={{header|Ring}}==
=={{header|Ring}}==
Retrieved from "https://rosettacode.org/wiki/Proper_divisors"