Rosetta Code

Prime decomposition: Difference between revisions

Page Discussion

Prime decomposition (view source)

Revision as of 10:25, 31 March 2024

193 bytes removed ,  2 months ago
→‎{{header|PowerShell}}
(→‎{{header|Elm}}: resurrected attempted edit)
(8 intermediate revisions by 6 users not shown)
Line 1:
{{task|Prime Numbers}}
[[Category:Arbitrary precision]]
{{omit from|GUISS}}
Line 1,676 ⟶ 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,618 ⟶ 2,639:
 
=={{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
 
--compositeNr = 84894624407 -- ==> 3067 4357 6353
 
-- compositeNr = 65536 -- = 2^16
 
compositeNr = 2*3*5*7*11*13*17 -- = 510510
 
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
 
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 (++) " "
 
-- Driver program to test above function
 
-- compositeNr = 84894624407
 
--      result = 3067 4357 6353
</syntaxhighlight>
{{out}}
Prime factors: 3067 4357 6353 from number 84894624407
 
=={{header|Elixir}}==
Line 4,668 ⟶ 4,636:
$prime
}
"$(prime-decomposition 12)"
"$(prime-decomposition 100)"
</syntaxhighlight>
<b>Output:</b>
Line 4,676 ⟶ 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 5,180 ⟶ 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 5,230 ⟶ 5,258:
 
<pre style="font-size:75%;height:160ex">
 
1 (0) prime factors: {unity}
2 (1) prime factors: [prime] 2
Line 5,356 ⟶ 5,385:
 
<pre style="font-size:75%>
 
3 (1) prime factors: [prime] 3
7 (1) prime factors: [prime] 7
Line 5,368 ⟶ 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,432 ⟶ 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,472 ⟶ 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 6,403 ⟶ 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/348799...363088"