Anonymous user
Count in factors: Difference between revisions
m
→{{header|REXX}}: increased the hardcode factorizations, added a 2nd REXX version.
m (→{{header|REXX}}: added a 3rd output (# primes < 100k).) |
m (→{{header|REXX}}: increased the hardcode factorizations, added a 2nd REXX version.) |
||
Line 2,522:
=={{header|REXX}}==
===simple approach===
It couldn't be determined if the showing of the '''x''' (for multiplication) was a strict requirement or whether
<br>there are (or can be) blanks surrounding the '''x''' (blanks were assumed for this example for readability).
Line 2,530 ⟶ 2,531:
'''sp=0''' will remove all blanks around the '''x'''.
<br>Also, as per the task's requirements, the prime factors of '''1''' (unity) will be listed as '''1''',▼
▲Also, as per the task's requirements, the prime factors of '''1''' (unity) will be listed as '''1''',
<br>even though, strictly speaking, it should be '''null'''. The same applies to '''0'''.
Line 2,555:
exit /*stick a fork in it, we're all done. */
/*────────────────────────────────────────────────────────────────────────────*/
factr: procedure; parse arg
do while z// 2==0; $=$ 'x 2' ; z=z% 2;
do while z// 3==0; $=$ 'x 3' ; z=z% 3;
do while z// 5==0; $=$ 'x 5' ; z=z% 5;
do while z// 7==0; $=$ 'x 7' ; z=z% 7; end /* " " " " 7 */
do
do y=0 by 2 while j<=z /*perform when Z isn't reduced enough.*/
j=j+2+y//4 /*insure that J isn't divisible by 3.*/
parse var j '' -1 _ /*obtain the last decimal digit of J. */
if _==5 then iterate /*fast check for divisible by five. */
if
▲ if j*j>q then leave /*are we higher than the √ Q ? */
do while z//j==0; $=$ 'x' j; z=z%j; end /*maybe add a prime factor.*/
end /*y*/
Line 2,623 ⟶ 2,625:
9592 primes found.
</pre>
===using integer SQRT===
This REXX version computes the ''integer square root'' of the integer being factor (to limit the range of factors),
<br>this makes this version slightly faster than the 1<sup>st</sup> REXX version.
Note that the '''integer square root''' section of code doesn't use any floating point numbers, just integers.
<lang rexx>/*REXX program lists the prime factors of a specified integer (or a range).*/
@.=left('',8); @.0='{unity} '; @.1='[prime] '; X='x' /*some tags and literals.*/
parse arg low high . /*get optional arguments from the C.L. */
if low=='' then do;low=1;high=40; end /*No LOW & HIGH? Then use the default.*/
if high=='' then high=low; tell=high>0 /*No HIGH? " " " " */
w=length(high); high=abs(high) /*get maximum width for pretty output. */
numeric digits max(9,w+1) /*maybe bump the precision of numbers. */
sp=1 /*1: allows spaces around the "x". */
#=0 /*the number of primes found (so far). */
do n=low to high; f=factr(n) /*process a single number or a range.*/
p=words(translate(f,,'x')) -(n==1) /*P: is the number of prime factors. */
if p==1 then #=#+1 /*bump the primes counter (exclude N=1)*/
if tell then say right(n,w) '=' @.p space(f,sp) /*show if prime & factors.*/
end /*n*/ /*if SP=0, then no spaces around the X.*/
say
say right(#,w) ' primes found.' /*display the number of primes found. */
exit /*stick a fork in it, we're all done. */
/*────────────────────────────────────────────────────────────────────────────*/
factr: procedure; parse arg z 1 n,$; if z<2 then return z
do while z// 2==0; $=$ 'x 2' ; z=z% 2; end /*maybe add factor of 2 */
do while z// 3==0; $=$ 'x 3' ; z=z% 3; end /* " " " " 3 */
do while z// 5==0; $=$ 'x 5' ; z=z% 5; end /* " " " " 5 */
do while z// 7==0; $=$ 'x 7' ; z=z% 7; end /* " " " " 7 */
do while z//11==0; $=$ 'x 11'; z=z%11; end /* " " " " 11 */
j=11 /*start the DO loop at J+2 (13)*/
t=z; r=0; q=1; do while q<=t; q=q*4; end /*R will be iSqrt of Z*/
do while q>1; q=q%4; _=t-r-q; r=r%2; if _>=0 then do; t=_; r=r+q; end
end /*while ···*/ /* [↑] compute the integer SQRT of Z. */
j=j+2+y//4 /*insure that J isn't divisible by 3.*/
parse var j '' -1 _ /*obtain the last decimal digit of J. */
if _==5 then iterate /*fast check for divisible by five. */
do while z//j==0; $=$ 'x' j; z=z%j; end /*maybe add a prime factor.*/
end /*y*/
if z==1 then z= /*if residual is unity, then nullify it*/
return strip( strip( $ 'x' z), , 'x') /*elide a possible leading (extra) "x".*/</lang>
'''output''' is identical to the 1<sup>st</sup> REXX version. <br><br>
=={{header|Ruby}}==
|