Rosetta Code

Prime decomposition: Difference between revisions

Page Discussion

Prime decomposition (view source)

Revision as of 10:25, 31 March 2024

6,034 bytes added ,  1 month ago
→‎{{header|PowerShell}}
 
(18 intermediate revisions by 11 users not shown)
Line 973:
 
=={{header|BASIC}}==
==={{header|ANSI BASIC}}===
{{trans|XPL0}}
{{works with|Decimal BASIC}}
<syntaxhighlight lang="basic">
100 PROGRAM PrimeDecomposition
110 REM -(2^31) has most prime factors (31 twos) than other 32-bit signed integer.
120 DIM Facs(0 TO 30)
130 INPUT PROMPT "Enter a number: ": N
140 CALL CalcFacs(N, Facs, FacsCnt)
150 REM There is at least one factor
160 FOR I = 0 TO FacsCnt - 1
170 PRINT Facs(I);
180 NEXT I
190 PRINT
200 END
210 REM **
220 EXTERNAL SUB CalcFacs(N, Facs(), FacsCnt)
230 LET N = ABS(N)
240 LET FacsCnt = 0
250 IF N >= 2 THEN
260 LET I = 2
270 DO WHILE I * I <= N
280 IF MOD(N, I) = 0 THEN
290 LET N = INT(N / I)
300 LET Facs(FacsCnt) = I
310 LET FacsCnt = FacsCnt + 1
320 LET I = 2
330 ELSE
340 LET I = I + 1
350 END IF
360 LOOP
370 LET Facs(FacsCnt) = N
380 LET FacsCnt = FacsCnt + 1
390 END IF
400 END SUB
</syntaxhighlight>
{{out}} 3 runs.
<pre>
Enter a number: 32
2 2 2 2 2
</pre>
<pre>
Enter a number: 2520
2 2 2 3 3 5 7
</pre>
<pre>
Enter a number: 13
13
</pre>
 
==={{header|Applesoft BASIC}}===
<syntaxhighlight lang="applesoftbasic">9040 PF(0) = 0 : SC = 0
Line 1,062 ⟶ 1,112:
9220 i=i/ca
9230 RETURN</syntaxhighlight>
 
==={{header|Craft Basic}}===
<syntaxhighlight lang="basic">define limit = 20, loops = 0
 
dim list[limit]
 
input "loops?", loops
 
for x = 1 to loops
 
let n = x
print n, " : ",
gosub collectprimefactors
 
for y = 0 to c
 
if list[y] then
 
print list[y], " ",
let list[y] = 0
 
endif
 
next y
 
print ""
 
next x
 
end
 
sub collectprimefactors
 
let c = 0
 
do
 
if int(n mod 2) = 0 then
 
let n = int(n / 2)
let list[c] = 2
let c = c + 1
 
endif
 
wait
 
loop int(n mod 2) = 0
 
for i = 3 to sqrt(n) step 2
 
do
 
if int(n mod i) = 0 then
 
let n = int(n / i)
let list[c] = i
let c = c + 1
 
endif
 
wait
 
loop int(n mod i) = 0
 
next i
 
if n > 2 then
 
let list[c] = n
let c = c + 1
 
endif
 
return</syntaxhighlight>
{{out| Output}}<pre>
loops? 20
1 :
2 : 2
3 : 3
4 : 2 2
5 : 5
6 : 2 3
7 : 7
8 : 2 2 2
9 : 3 3
10 : 2 5
11 : 11
12 : 2 2 3
13 : 13
14 : 2 7
15 : 3 5
16 : 2 2 2 2
17 : 17
18 : 2 3 3
19 : 19
20 : 2 2 5
</pre>
 
==={{header|FreeBASIC}}===
Line 1,529 ⟶ 1,677:
1232126 ⟨ 2 7 17 31 167 ⟩
┘</syntaxhighlight>
 
=={{header|Bruijn}}==
{{trans|Haskell}}
<syntaxhighlight lang="bruijn">
:import std/Combinator .
:import std/List .
:import std/Math .
 
factors \divs primes
divs y [[&[[&[[3 ⋅ 3 >? 4 case-1 (=?0 case-2 case-3)]] (quot-rem 2 1)]]]]
case-1 4 >? (+1) {}4 empty
case-2 3 : (5 1 (3 : 2))
case-3 5 4 2
 
main [factors <$> ({ (+42) → (+50) })]
</syntaxhighlight>
{{out}}
<code>
?> {{2t, 3t, 7t}, {43t}, {2t, 2t, 11t}, {3t, 3t, 5t}, {2t, 23t}, {47t}, {2t, 2t, 2t, 2t, 3t}, {7t, 7t}, {2t, 5t, 5t}}
</code>
 
=={{header|Burlesque}}==
Line 2,376 ⟶ 2,544:
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
funcproc decompose num . primes[] .
primes[] = [ ]
t = 2
Line 2,389 ⟶ 2,557:
primes[] &= num
.
call decompose 9007199254740991 r[]
print r[]
</syntaxhighlight>
Line 2,469 ⟶ 2,637:
 
{{out}}<pre>[71,839,1471,6857]</pre>
 
=={{header|Elm}}==
<syntaxhighlight lang="elm" line="1">
module Main exposing (main)
 
import Html exposing (Html, div, h1, text)
import Html.Attributes exposing (style)
 
-- See live:
-- <nowiki>https://ellie-app.com/pMYxVPQ4fvca1</nowiki>
 
accumulator : List Int
accumulator =
    []
 
compositeNr = 84894624407
 
ts =
    showFactors compositeNr 2 accumulator
 
 
main =
        div
            [ style "margin" "5%"
            , style "font-size" "1.5em"
            , style "color" "blue"
            ]
            [ h1 [] [ text "Prime Factorizer" ]
            , text
                ("Prime factors: "
                    ++ listAsString ts
                    ++ " from number "
                    ++ String.fromInt (List.product ts)
                )
            ]
 
 
showFactors : Int -> Int -> List Int -> List Int
showFactors number factor acc =
    if number < 2 then
        acc
        -- returns the final result if number < 2
    else if
        modBy factor number == 0
        -- modulo used to get prime factors
then let
            v2 : List Int
            v2 =
                factor :: acc
            number2 : Int
            number2 =
                number // factor
        in
        showFactors number2 factor v2
        -- recursive call
        -- this modulus function is used
        -- in order to output factor !=2
    else
        let
            factor2 : Int
            factor2 =
                factor + 1
        in
        showFactors number factor2 acc
 
listAsString : List Int -> String
listAsString myList =
    List.map String.fromInt myList
        |> List.map (\el -> " " ++ el)
        |> List.foldl (++) " "
 
</syntaxhighlight>
{{out}}
Prime factors: 3067 4357 6353 from number 84894624407
 
=={{header|Elixir}}==
Line 3,698 ⟶ 3,940:
prime_dec(2^4*3^5*5*7^2);
/* [2, 2, 2, 2, 3, 3, 3, 3, 3, 5, 7, 7] */</syntaxhighlight>
 
=={{header|Modula-2}}==
{{trans|XPL0|<code>CARDINAL</code> (unsigned integer) used instead of signed integer.}}
{{works with|ADW Modula-2|any (Compile with the linker option ''Console Application'').}}
<syntaxhighlight lang="modula2">
MODULE PrimeDecomposition;
 
FROM STextIO IMPORT
SkipLine, WriteLn, WriteString;
FROM SWholeIO IMPORT
ReadCard, WriteInt;
 
CONST
MaxFacIndex = 31;
(* 2^31 has most prime factors (31 twos) than other 32-bit unsigned integer. *)
 
TYPE
TFacs = ARRAY [0 .. MaxFacIndex] OF CARDINAL;
 
VAR
Facs: TFacs;
I, N, FacsCnt: CARDINAL;
PROCEDURE CalcFacs(N: CARDINAL; VAR Facs: TFacs; VAR FacsCnt: CARDINAL);
VAR
I: CARDINAL;
BEGIN
FacsCnt := 0;
IF N >= 2 THEN
I := 2;
WHILE I * I <= N DO
IF N MOD I = 0 THEN
N := N DIV I;
Facs[FacsCnt] := I;
FacsCnt := FacsCnt + 1;
I := 2
ELSE
I := I + 1
END
END;
Facs[FacsCnt] := N;
FacsCnt := FacsCnt + 1
END;
END CalcFacs;
 
BEGIN
WriteString("Enter a number: ");
ReadCard(N);
SkipLine;
CalcFacs(N, Facs, FacsCnt);
(* There is at least one factor *)
IF FacsCnt > 1 THEN
FOR I := 0 TO FacsCnt - 2 DO
WriteInt(Facs[I], 1);
WriteString(" ")
END;
END;
WriteInt(Facs[FacsCnt - 1], 1);
WriteLn
END PrimeDecomposition.
</syntaxhighlight>
{{out}} 3 runs.
<pre>
Enter a number: 32
2 2 2 2 2
</pre>
<pre>
Enter a number: 2520
2 2 2 3 3 5 7
</pre>
<pre>
Enter a number: 13
13
</pre>
 
=={{header|MUMPS}}==
Line 4,320 ⟶ 4,636:
$prime
}
"$(prime-decomposition 12)"
"$(prime-decomposition 100)"
</syntaxhighlight>
<b>Output:</b>
Line 4,328 ⟶ 4,644:
2 2 5 5
</pre>
Alternative version, significantly faster with big numbers
<syntaxhighlight lang="powershell">
function prime-decomposition ($n) {
$values = [System.Collections.Generic.List[string]]::new()
while ((($n % 2) -eq 0) -and ($n -gt 2)) {
$values.Add(2)
$n /= 2
}
for ($i = 3; $n -ge ($i * $i); $i += 2) {
if (($n % $i) -eq 0){
$values.Add($i)
$n /= $i
$i -= 2
}
}
$values.Add($n)
return $values
}
"$(prime-decomposition 1000000)"
</syntaxhighlight>
 
=={{header|Prolog}}==
Line 4,618 ⟶ 4,954:
=={{header|Quackery}}==
 
<code>prime</code> is defined at [[Miller-Rabin primality test#Quackery]].
<syntaxhighlight lang="quackery"> [ [] swap
 
<syntaxhighlight lang="quackery"> [ dup prime iff
nested done
[] swap
dup times
[ [ dup i^ 2 + /modprime
not if done
[ dup i^ 2 + /mod
0 = while
nip dip
Line 4,627 ⟶ 4,969:
drop
dup 1 = if conclude ]
drop ] is primefactors ( n --> [ )</syntaxhighlight>
 
1047552 primefactors echo</syntaxhighlight>
 
{{out}}
Line 4,828 ⟶ 5,168:
A method exists in this REXX program to also test Mersenne-type numbers &nbsp; <big>(2<sup>n</sup> - 1)</big>.
 
Since the majority of computing time is spent looking for primes, that part of the program was
<br>optimized somewhat (but could be extended if more optimization is wanted).
<syntaxhighlight lang="rexx"></*REXX pgm does prime decomposition of a range of positive integers (with a prime count)*/syntaxhighlight>
/*REXX pgm does prime decomposition of a range of positive integers (with a prime count)*/
numeric digits 1000 /*handle thousand digits for the powers*/
parseNumeric argDigits 1000 bot top step base add /*gethandle optionalthousand argumentsdigits fromFor the C.L. powers*/
ifParse Arg bot=='' top then do;step bot=1; top=100; end base add /*noget optional BOTarguments given? Then usefrom the defaultC.L. */
If bot='?' Then Do
if top=='' then top=bot /* " TOP? " " " " " */
Say 'rexx pfoo bot top step base add'
if step=='' then step= 1 /* " STEP? " " " " " */
Exit
if add =='' then add= -1 /* " ADD? " " " " " */
End
tell= top>0; top=abs(top) /*if TOP is negative, suppress displays*/
wIf bot==length(top)'' Then /* no arguments given /*get maximum width for aligned display*/
Parse Value 1 100 With bot top /* set default range .*/
if base\=='' then w=length(base**top) /*will be testing powers of two later? */
If top=='' Then top=bot /* process one number */
@.=left('', 7); @.0="{unity}"; @.1='[prime]' /*some literals: pad; prime (or not).*/
numericIf digitsstep=='' max(9,Then w+step=1) /* step=2 to process only odd numbers /*maybe increase the digits precision. */
#=0If add =='' Then add=-1 /* for Mersenne tests /*#: is the number of primes found. */
tell=top>0 do n=bot to top by step /*process a single numberIf TOP oris negative, asuppress range.displays*/
top=abs(top)
?=n; if base\=='' then ?=base**n + add /*should we perform a "Mercenne" test? */
w=length(top) pf=factr(?); f=words(pf) /*get primemaximum factors;width numberFor ofaligned factors.display*/
If base\=='' Then
if f==1 then #=#+1 /*Is N prime? Then bump prime counter.*/
w=length(base**top) if tell then say right(?,w) right('('f")",9) 'prime/*will factors:be ' @.ftesting powers of two later? pf*/
tag.=left('', 7) /*some literals: pad; prime (or not).*/
end /*n*/
tag.0='{unity}'
say
tag.1='[prime]'
ps= 'primes'; if p==1 then ps= "prime" /*setup for proper English in sentence.*/
sayNumeric rightDigits max(#9, w+9+1) ps 'found.' /*displaymaybe increase the numberdigits of primes foundprecision. */
exit np=0 /*sticknp: a fork in it,is the we'renumber allof doneprimes found. */
Do n=bot To top by step /*process a single number or a range. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
?=n
factr: procedure; parse arg x 1 d,$ /*set X, D to argument 1; $ to null.*/
if x If base\==1 then return '' Then /*handleshould thewe specialperform casea of X = 1.'Mersenne' test? */
?=base**n+add
do while x//2==0; $=$ 2; x=x%2; end /*append all the 2 factors of new X.*/
pf=factr(?) do while x//3==0; $=$ 3; x=x%3; end /* " "/* get prime "factors 3 " " " " */
f=words(pf) do while x//5==0; $=$ 5; x=x%5; end /* " " " /* 5number of prime factors " " " " */
If f=1 Then do while x//7==0; $=$ 7; x=x%7; end /* " " /* " If the 7number is prime " " " " */
np=np+1 /* Then bump prime counter ___*/
If tell Then
q=1; do while q<=x; q=q*4; end /*these two lines compute integer √ X */
Say right(?,w) right('('f')',9) 'prime factors: ' tag.f pf
r=0; do while q>1; q=q%4; _=d-r-q; r=r%2; if _>=0 then do; d=_; r=r+q; end; end
End /*n*/
Say ''
ps='prime'
If f>1 Then ps=ps's' /*setup For proper English in sentence.*/
Say right(np, w+9+1) ps 'found.' /*display the number of primes found. */
Exit /*stick a fork in it, we're all done. */
/*---------------------------------------------------------------------------*/
factr: Procedure
Parse Arg x 1 d,pl /*set X, D to argument 1, pl to null */
If x==1 Then Return '' /*handle the special case of X=1. */
primes=2 3 5 7
Do While primes>'' /* first check the small primes */
Parse Var primes prime primes
Do While x//prime==0
pl=pl prime
x=x%prime
End
End
r=isqrt(x)
Do j=11 by 6 To r /*insure that J isn't divisible by 3. */
Parse var j '' -1 _ /*obtain the last decimal digit of J. */
If _\==5 Then Do
Do While x//j==0
pl=pl j
x=x%j
End /*maybe reduce by J. */
End
If _ ==3 Then Iterate /*If next Y is divisible by 5? Skip. */
y=j+2
Do While x//y==0
pl=pl y
x=x%y
End /*maybe reduce by y. */
End /*j*/
 
If do jx==11 by 6 to r 1 Then Return pl /*insureIs thatresidual=unity? Then J isndon't divisible by 3append.*/
parse var j '' -1 _ Return pl x /*obtainreturn the last decimalpl digit of with Jappended residual. */
 
if _\==5 then do while x//j==0; $=$ j; x=x%j; end /*maybe reduce by J. */
isqrt: Procedure
if _ ==3 then iterate /*Is next Y is divisible by 5? Skip.*/
Parse Arg x
y=j+2; do while x//y==0; $=$ y; x=x%y; end /*maybe reduce by J. */
x=abs(x)
end /*j*/
Parse Value 0 x with lo hi
/* [↓] The $ list has a leading blank.*/
Do While lo<=hi
if x==1 then return $ /*Is residual=unity? Then don't append.*/
t=(lo+hi)%2
return $ x /*return $ with appended residual. */</syntaxhighlight>
If t**2>x Then
hi=t-1
Else
lo=t+1
End
Return t
'''output''' &nbsp; when using the default input of: &nbsp; <tt> 1 &nbsp; 100 </tt>
 
Line 4,878 ⟶ 5,258:
 
<pre style="font-size:75%;height:160ex">
 
1 (0) prime factors: {unity}
2 (1) prime factors: [prime] 2
Line 5,004 ⟶ 5,385:
 
<pre style="font-size:75%>
 
3 (1) prime factors: [prime] 3
7 (1) prime factors: [prime] 7
Line 5,016 ⟶ 5,398:
4095 (5) prime factors: 3 3 5 7 13
8191 (1) prime factors: [prime] 8191
16383 (23) prime factors: 3 546143 127
32767 (23) prime factors: 7 468131 151
65535 (4) prime factors: 3 5 17 257
131071 (1) prime factors: [prime] 131071
262143 (56) prime factors: 3 3 3 7 138719 73
524287 (1) prime factors: [prime] 524287
1048575 (6) prime factors: 3 5 5 11 41 31 41
2097151 (34) prime factors: 7 7 42799127 337
4194303 (4) prime factors: 3 23 89 683
8388607 (2) prime factors: 47 178481
16777215 (7) prime factors: 3 3 5 7 13 17 241
33554431 (13) prime factors: [prime] 33554431 31 601 1801
67108863 (23) prime factors: 3 223696212731 8191
134217727 (23) prime factors: 7 1917396173 262657
268435455 (56) prime factors: 3 5 29 43 113 5461127
536870911 (3) prime factors: 233 1103 2089
1073741823 (57) prime factors: 3 3 7 11 154941131 151 331
2147483647 (1) prime factors: [prime] 2147483647
4294967295 (5) prime factors: 3 5 17 257 65537
8589934591 (4) prime factors: 7 23 89 599479
17179869183 (3) prime factors: 3 43691 131071
34359738367 (34) prime factors: 31 71 122921127 3937122921
68719476735 (710) prime factors: 3 3 3 5 7 13 559377119 37 73 109
137438953471 (12) prime factors: [prime] 137438953471 223 616318177
274877906943 (23) prime factors: 3 91625968981174763 524287
549755813887 (24) prime factors: 7 7853654484179 8191 121369
1099511627775 (78) prime factors: 3 5 5 11 17 31 41 191211161681
2199023255551 (2) prime factors: 13367 164511353
4398046511103 (58) prime factors: 3 3 7 7 997289458343 127 337 5419
8796093022207 (3) prime factors: 431 9719 2099863
17592186044415 (67) prime factors: 3 5 23 89 397 683 8388612113
35184372088831 (26) prime factors: 7 502633886983331 73 151 631 23311
70368744177663 (4) prime factors: 3 47 178481 2796203
140737488355327 (23) prime factors: 2351 598628193774513 13264529
281474976710655 (810) prime factors: 3 3 5 7 13 17 97 241 257 15732721673
562949953421311 (12) prime factors: [prime] 562949953421311 127 4432676798593
1125899906842623 (47) prime factors: 3 11 31 251 135928999981601 1801 4051
 
11 8 primes found.
</pre>
'''output''' &nbsp; when using the input of: &nbsp; <tt> 1 &nbsp; 50 &nbsp; 1 &nbsp; 2 &nbsp; +1 </tt>
Line 5,080 ⟶ 5,462:
65537 (1) prime factors: [prime] 65537
131073 (2) prime factors: 3 43691
262145 (34) prime factors: 5 13 403337 109
524289 (2) prime factors: 3 174763
1048577 (2) prime factors: 17 61681
2097153 (34) prime factors: 3 3 23301743 5419
4194305 (23) prime factors: 5 838861397 2113
8388609 (2) prime factors: 3 2796203
16777217 (23) prime factors: 97 257 65281673
33554433 (4) prime factors: 3 11 251 4051
67108865 (4) prime factors: 5 53 1613 157 1613
134217729 (56) prime factors: 3 3 3 3 165700919 87211
268435457 (2) prime factors: 17 15790321
536870913 (3) prime factors: 3 59 3033169
1073741825 (56) prime factors: 5 5 13 41 8058161 1321
2147483649 (2) prime factors: 3 715827883
4294967297 (2) prime factors: 641 6700417
8589934593 (45) prime factors: 3 3 67 683 139741920857
17179869185 (4) prime factors: 5 137 953 26317
34359738369 (5) prime factors: 3 11 43 281 86171 43
68719476737 (24) prime factors: 17 4042322161241 433 38737
137438953473 (23) prime factors: 3 458129844911777 25781083
274877906945 (24) prime factors: 5 54975581389229 457 525313
549755813889 (34) prime factors: 3 3 610839793212731 22366891
1099511627777 (2) prime factors: 257 4278255361
2199023255553 (3) prime factors: 3 83 8831418697
4398046511105 (56) prime factors: 5 13 29 113 206476211429 14449
8796093022209 (2) prime factors: 3 2932031007403
17592186044417 (3) prime factors: 17 353 2931542417
35184372088833 (57) prime factors: 3 3 3 11 11846589928919 331 18837001
70368744177665 (45) prime factors: 5 277 1013 302691657 45898930269
140737488355329 (23) prime factors: 3 46912496118443283 165768537521
281474976710657 (23) prime factors: 193 65537 429490176122253377
562949953421313 (23) prime factors: 3 18764998447377143 4363953127297
1125899906842625 (67) prime factors: 5 5 5 41 101 21751266018101 268501
 
5 primes found.
Line 5,120 ⟶ 5,502:
This REXX version is about &nbsp; '''20%''' &nbsp; faster than the 1<sup>st</sup> REXX version when factoring one million numbers.
<syntaxhighlight lang="rexx">/*REXX pgm does prime decomposition of a range of positive integers (with a prime count)*/
numericNumeric digitsDigits 1000 /*handle thousand digits forFor the powers*/
parseParse argArg bot top step base add /*get optional arguments from the C.L. */
If bot='?' Then Do
if bot=='' then do; bot=1; top=100; end /*no BOT given? Then use the default.*/
Say 'rexx pfoo bot top step base add'
if top=='' then top=bot /* " TOP? " " " " " */
Exit
if step=='' then step= 1 /* " STEP? " " " " " */
End
if add =='' then add= -1 /* " ADD? " " " " " */
tellIf bot=='' top>0;Then top=abs(top) /*if TOPno arguments given is negative, suppress displays*/
w=length(top) Parse Value 1 100 With bot top /* set default range /*get maximum width for aligned display.*/
ifIf base\top=='' Then then w=length(base**top)=bot /*will beprocess one number testing powers of two later? */
If step=='' Then step=1 /* step=2 to process only odd numbers */
@.=left('', 7); @.0="{unity}"; @.1='[prime]' /*some literals: pad; prime (or not).*/
numericIf digitsadd max(9,=='' w+Then add=-1) /* for Mersenne tests /*maybe increase the digits precision. */
#tell=top>0 /*#: If TOP is the number of primesnegative, found.suppress displays*/
top=abs(top)
do n=bot to top by step /*process a single number or a range.*/
w=length(top) ?=n; if base\=='' then ?=base**n + add /*should weget performmaximum awidth "Mercenne"For test?aligned display*/
If base\=='' Then
pf=factr(?); f=words(pf) /*get prime factors; number of factors.*/
if fw==1 then #=#+1 length(base**top) /*Iswill Nbe prime?testing powers Thenof bumptwo primelater? counter.*/
tag.=left('', 7) if tell then say right(?,w) right('('f")",9) 'prime factors: ' /*some literals: @.fpad; prime (or pfnot).*/
tag.0='{unity}'
end /*n*/
tag.1='[prime]'
say
ps=Numeric 'primes';Digits max(9,w+1) if p==1 then ps= "prime" /*setupmaybe forincrease properthe Englishdigits in sentenceprecision. */
saynp=0 right(#, w+9+1) ps 'found.' /*displaynp: is the number of primes found. */
exit Do n=bot To top by step /*stickprocess a forksingle innumber it,or a we'rerange. all done. */
?=n
/*──────────────────────────────────────────────────────────────────────────────────────*/
factr: procedure; If parsebase\=='' argThen x 1 d,$ /*set X, D /*should to argument 1;we perform $a 'Mersenne' totest? null.*/
?=base**n+add
if x==1 then return '' /*handle the special case of X = 1. */
pf=factr(?) do while x// 2==0; $=$ 2; x=x%2; end /*append allget prime factors the 2 factors of new X.*/
f=words(pf) do while x// 3==0; $=$ 3; x=x%3; end /* " " " /* 3number of prime factors " " " " */
If f=1 Then do while x// 5==0; $=$ 5; x=x%5; end /* " " /* " If the 5number is prime " " " " */
np=np+1 do while x// 7==0; $=$ 7; x=x%7; end /* " " " /* 7Then bump prime counter " " " " */
If tell Then
do while x//11==0; $=$ 11; x=x%11; end /* " " " 11 " " " " */ /* ◄■■■■ added.*/
Say right(?,w) right('('f')',9) 'prime factors: ' tag.f pf
do while x//13==0; $=$ 13; x=x%13; end /* " " " 13 " " " " */ /* ◄■■■■ added.*/
End /*n*/
do while x//17==0; $=$ 17; x=x%17; end /* " " " 17 " " " " */ /* ◄■■■■ added.*/
Say ''
do while x//19==0; $=$ 19; x=x%19; end /* " " " 19 " " " " */ /* ◄■■■■ added.*/
ps='prime'
do while x//23==0; $=$ 23; x=x%23; end /* " " " 23 " " " " */ /* ◄■■■■ added.*/
If f>1 Then ps=ps's' /*setup For proper English in ___sentence.*/
Say right(np, w+9+1) ps 'found.' /*display the number of primes found. */
q=1; do while q<=x; q=q*4; end /*these two lines compute integer √ X */
Exit /*stick a fork in it, we're all done. */
r=0; do while q>1; q=q%4; _=d-r-q; r=r%2; if _>=0 then do; d=_; r=r+q; end; end
/*---------------------------------------------------------------------------*/
factr: Procedure
Parse Arg x 1 d,pl /*set X, D to argument 1, pl to null */
If x==1 Then Return '' /*handle the special case of X=1. */
primes=2 3 5 7 11 13 17 19 23
Do While primes>'' /* first check the small primes */
Parse Var primes prime primes
Do While x//prime==0
pl=pl prime
x=x%prime
End
End
r=isqrt(x)
Do j=29 by 6 To r /*insure that J isn't divisible by 3.*/
Parse var j '' -1 _ /*obtain the last decimal digit of J. */
If _\==5 Then Do
Do While x//j==0
pl=pl j
x=x%j
End /*maybe reduce by J. */
End
If _ ==3 Then Iterate /*If next Y is divisible by 5? Skip. */
y=j+2
Do While x//y==0
pl=pl y
x=x%y
End /*maybe reduce by y. */
End /*j*/
If x==1 Then Return pl /*Is residual=unity? Then don't append.*/
Return pl x /*return pl with appended residual.*/
 
isqrt: Procedure
do j=29 by 6 to r /*insure that J isn't divisible by 3.*/ /* ◄■■■■ changed.*/
Parse Arg x
parse var j '' -1 _ /*obtain the last decimal digit of J. */
x=abs(x)
if _\==5 then do while x//j==0; $=$ j; x=x%j; end /*maybe reduce by J. */
Parse Value 0 x with lo hi
if _ ==3 then iterate /*Is next Y is divisible by 5? Skip.*/
Do While lo<=hi
y=j+2; do while x//y==0; $=$ y; x=x%y; end /*maybe reduce by J. */
end /*j*/t=(lo+hi)%2
If t**2>x Then
/* [↓] The $ list has a leading blank.*/
hi=t-1
if x==1 then return $ /*Is residual=unity? Then don't append.*/
Else
return $ x /*return $ with appended residual. */</syntaxhighlight>
lo=t+1
End
Return t</syntaxhighlight>
'''output''' &nbsp; is identical to the 1<sup>st</sup> REXX version. <br><br>
 
Line 5,195 ⟶ 5,610:
=={{header|RPL}}==
≪ { } SWAP DUP √ CEIL → lim
≪ 2
≪ 2 '''WHILE''' OVER 1 > OVER lim ≤ AND '''REPEAT'''
'''WHILE''' OVER 1 > OVER lim ≤ AND '''REPEAT'''
DUP2 /
'''IF''' DUP FP '''THEN''' DROP DUP 2 ≠ + 1 +
'''THEN''' DROP DUP 2 ≠ + 1 +
'''ELSE''' SWAP ROT DROP ROT OVER + ROT ROT '''END'''
'''END''' DROP
DROP
'''IF''' DUP 1 ≠ '''THEN''' + '''ELSE''' DROP '''END'''
≫ ≫ ‘'''PDIV'''’ STO
≫
 
≫ ‘'''DIVS'''’ STO
1048 '''PDIV'''
{{out}}
<pre>
1: { 2 2 2 131 }
</pre>
===Version for binary integers===
{{trans|Forth}}
≪ { } → pdiv
≪ #2
'''WHILE''' DUP2 DUP * ≥ '''REPEAT'''
'''IF''' DUP2 / LAST 3 PICK * -
'''THEN''' DROP 1 + #1 OR
'''ELSE''' ROT DROP SWAP pdiv OVER + 'pdiv' STO '''END'''
'''END''' DROP pdiv SWAP +
≫ ≫ ‘'''PDIVB'''’ STO
 
2#1048 28 ^ 1 - ‘'''DIVSPDIVB'''’
{{out}}
<pre>
1: { 3#2d 5#2d 29#2d 43 113 127#131d }
</pre>
 
Line 6,035 ⟶ 6,466:
{{libheader|Wren-fmt}}
The examples are borrowed from the Go solution.
<syntaxhighlight lang="ecmascriptwren">import "./big" for BigInt
import "./fmt" for Fmt
 
var vals = [1 << 31, 1234567, 333333, 987653, 2 * 3 * 5 * 7 * 11 * 13 * 17]
Lijice4777
1

edit

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/339964...363088"