Prime decomposition: Difference between revisions
→{{header|PowerShell}}
Lijice4777 (talk | contribs) |
|||
(16 intermediate revisions by 10 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,389 ⟶ 2,557:
primes[] &= num
.
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
"$(prime-decomposition
</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"> [ dup prime iff
nested done
[] swap
dup times
[
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>
{{out}}
Line 4,828 ⟶ 5,168:
A method exists in this REXX program to also test Mersenne-type numbers <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)*/
If bot='?' Then Do
Say 'rexx pfoo bot top step base add'
Exit
End
Parse Value 1 100 With bot top /* set default range .*/
If top=='' Then top=bot /* process one number */
tell=top>0
top=abs(top)
w=length(top)
If base\=='' Then
w=length(base**top)
tag.=left('', 7) /*some literals: pad; prime (or not).*/
tag.0='{unity}'
tag.1='[prime]'
Do n=bot To top by step /*process a single number or a range. */
?=n
?=base**n+add
pf=factr(?)
f=words(pf)
If f=1 Then
If tell Then
Say right(?,w) right('('f')',9) 'prime factors: ' tag.f pf
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
isqrt: Procedure
Parse Arg x
x=abs(x)
Parse Value 0 x with lo hi
Do While lo<=hi
t=(lo+hi)%2
If t**2>x Then
hi=t-1
Else
lo=t+1
End
Return t
'''output''' when using the default input of: <tt> 1 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 (
32767 (
65535 (4) prime factors: 3 5 17 257
131071 (1) prime factors: [prime] 131071
262143 (
524287 (1) prime factors: [prime] 524287
1048575 (6) prime factors: 3 5 5 11
2097151 (
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 (
67108863 (
134217727 (
268435455 (
536870911 (3) prime factors: 233 1103 2089
1073741823 (
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 (
68719476735
137438953471 (
274877906943 (
549755813887 (
1099511627775 (
2199023255551 (2) prime factors: 13367 164511353
4398046511103 (
8796093022207 (3) prime factors: 431 9719 2099863
17592186044415 (
35184372088831 (
70368744177663 (4) prime factors: 3 47 178481 2796203
140737488355327 (
281474976710655
562949953421311 (
1125899906842623 (
</pre>
'''output''' when using the input of: <tt> 1 50 1 2 +1 </tt>
Line 5,080 ⟶ 5,462:
65537 (1) prime factors: [prime] 65537
131073 (2) prime factors: 3 43691
262145 (
524289 (2) prime factors: 3 174763
1048577 (2) prime factors: 17 61681
2097153 (
4194305 (
8388609 (2) prime factors: 3 2796203
16777217 (
33554433 (4) prime factors: 3 11 251 4051
67108865 (4) prime factors: 5 53
134217729 (
268435457 (2) prime factors: 17 15790321
536870913 (3) prime factors: 3 59 3033169
1073741825 (
2147483649 (2) prime factors: 3 715827883
4294967297 (2) prime factors: 641 6700417
8589934593 (
17179869185 (4) prime factors: 5 137 953 26317
34359738369 (5) prime factors: 3 11 43 281 86171
68719476737 (
137438953473 (
274877906945 (
549755813889 (
1099511627777 (2) prime factors: 257 4278255361
2199023255553 (3) prime factors: 3 83 8831418697
4398046511105 (
8796093022209 (2) prime factors: 3 2932031007403
17592186044417 (3) prime factors: 17 353 2931542417
35184372088833 (
70368744177665 (
140737488355329 (
281474976710657 (
562949953421313 (
1125899906842625 (
5 primes found.
Line 5,120 ⟶ 5,502:
This REXX version is about '''20%''' 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)*/
If bot='?' Then Do
Say 'rexx pfoo bot top step base add'
Exit
End
If step=='' Then step=1 /* step=2 to process only odd numbers */
top=abs(top)
w=length(top)
If base\=='' Then
tag.=left('', 7)
tag.0='{unity}'
tag.1='[prime]'
?=n
?=base**n+add
pf=factr(?)
f=words(pf)
If f=1 Then
np=np+1
If tell Then
Say right(?,w) right('('f')',9) 'prime factors: ' tag.f pf
End /*n*/
Say ''
ps='prime'
If f>1 Then
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 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
Parse Arg x
x=abs(x)
Parse Value 0 x with lo hi
Do While lo<=hi
If t**2>x Then
hi=t-1
Else
lo=t+1
End
Return t</syntaxhighlight>
'''output''' is identical to the 1<sup>st</sup> REXX version. <br><br>
Line 6,051 ⟶ 6,466:
{{libheader|Wren-fmt}}
The examples are borrowed from the Go solution.
<syntaxhighlight lang="
import "./fmt" for Fmt
var vals = [1 << 31, 1234567, 333333, 987653, 2 * 3 * 5 * 7 * 11 * 13 * 17]
|