Prime decomposition: Difference between revisions
→{{header|PowerShell}}
Lijice4777 (talk | contribs) |
|||
(48 intermediate revisions by 20 users not shown) | |||
Line 37:
{{trans|D}}
<
[BigInt] result
V n = number
Line 58:
print(decompose(1023 * 1024))
print(decompose(2 * 3 * 5 * 7 * 11 * 11 * 13 * 17))
print(decompose(BigInt(16860167264933) * 179951))</
{{out}}
Line 77:
=={{header|360 Assembly}}==
For maximum compatibility, this program uses only the basic instruction set.
<
USING PRIMEDE,R13
B 80(R15) skip savearea
Line 152:
WDECO DS CL16
YREGS
END PRIMEDE</
{{out}}
<pre>
Line 160:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program primeDecomp64.s */
Line 386:
.include "../includeARM64.inc"
</syntaxhighlight>
{{Output}}
<pre>
Line 397:
=={{header|ABAP}}==
<
public
create public .
Line 449:
ENDIF.
endmethod.
ENDCLASS.</
=={{header|ACL2}}==
<
(defun prime-factors-r (n i)
Line 464:
(defun prime-factors (n)
(declare (xargs :mode :program))
(prime-factors-r n 2))</
=={{header|Ada}}==
Line 474:
This is the specification of the generic package '''Prime_Numbers''':
<
type Number is private;
Zero : Number;
Line 488:
function Decompose (N : Number) return Number_List;
function Is_Prime (N : Number) return Boolean;
end Prime_Numbers;</
The function Decompose first estimates the maximal result length as log<sub>2</sub> of the argument. Then it allocates the result and starts to enumerate divisors. It does not care to check if the divisors are prime, because non-prime divisors will be automatically excluded.
Line 494:
This is the implementation of the generic package '''Prime_Numbers''':
<
-- auxiliary (internal) functions
function First_Factor (N : Number; Start : Number) return Number is
Line 524:
function Is_Prime (N : Number) return Boolean is
(N > One and then First_Factor(N, Two)=N);
end Prime_Numbers;</
In the example provided, the package '''Prime_Numbers''' is instantiated with plain integer type:
<
procedure Test_Prime is
Line 545:
begin
Put (Decompose (12));
end Test_Prime;</
{{out}} (decomposition of 12):
Line 561:
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}
<
MODE LINT = LONG INT;
Line 663:
# OD # ));
done: EMPTY
)</
{{out}}
<pre>
Line 688:
=={{header|ALGOL-M}}==
Sadly, ALGOL-M does not allow arrays to be passed as parameters to procedures or functions, so the routine
must store its results in (and know the name of
<syntaxhighlight lang="algol">
BEGIN
Line 695:
INTEGER ARRAY FACTORS[1:16];
COMMENT
INTEGER FUNCTION MOD (P, Q);
INTEGER P, Q;
Line 734:
WRITE(I,":");
NFOUND := PRIMEFACTORS(I);
COMMENT - PRINT OUT THE FACTORS THAT WERE FOUND;
FOR K := 1 STEP 1 UNTIL NFOUND DO
BEGIN
Line 741 ⟶ 742:
END
</syntaxhighlight>
{{out}}
<pre>
Line 757 ⟶ 758:
99: 3 3 11
</pre>
=={{header|ALGOL W}}==
Algol W procedures can't return arrays, so an array to store the factors in must be passed as a parameter.
<syntaxhighlight lang="algolw">
begin % find the prime decompositionmtion of some integers %
% increments n and returns the new value %
integer procedure inc ( integer value result n ) ; begin n := n + 1; n end;
% divides n by d and returns the result %
integer procedure over ( integer value result n
; integer value d
) ; begin n := n div d; n end;
% sets the elements of f to the prime factors of n %
% the bounds of f should be 0 :: x where x is large enough to hold %
% all the factors, f( 0 ) will contain 6he number of factors %
procedure decompose ( integer value n; integer array f ( * ) ) ;
begin
integer d, v;
f( 0 ) := 0;
v := abs n;
if v > 0 and v rem 2 = 0 then begin
f( inc( f( 0 ) ) ) := 2;
while over( v, 2 ) > 0 and v rem 2 = 0 do f( inc( f( 0 ) ) ) := 2;
end if_2_divides_v ;
d := 3;
while d * d <= v do begin
if v rem d = 0 then begin
f( inc( f( 0 ) ) ) := d;
while over( v, d ) > 0 and v rem d = 0 do f( inc( f( 0 ) ) ) := d;
end if_d_divides_v ;
d := d + 2
end while_d_squared_le_v ;
if v > 1 then f( inc( f( 0 ) ) ) := v
end factorise ;
% some test cases %
for n := 0, 1, 7, 31, 127, 2047, 8191, 131071, 524287, 2520, 32767, 8855, 441421750 do begin
integer array f( 0 :: 20 );
decompose( n, f );
write( s_w := 0, n, ": " );
for fPos := 1 until f( 0 ) do writeon( i_w := 1, s_w := 0, " ", f( fPos ) );
end for_n ;
end.
</syntaxhighlight>
{{out}}
<pre>
0:
1:
7: 7
31: 31
127: 127
2047: 23 89
8191: 8191
131071: 131071
524287: 524287
2520: 2 2 2 3 3 5 7
32767: 7 31 151
8855: 5 7 11 23
441421750: 2 5 5 5 7 11 23 997
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">decompose: function [num][
facts: to [:string] factors.prime num
print [
Line 782 ⟶ 827:
]
loop 2..40 => decompose</
{{out}}
Line 827 ⟶ 872:
=={{header|AutoHotkey}}==
<
factor(n)
Line 843 ⟶ 888:
f++
}
}</
===Optimized Version===
{{trans|JavaScript}}
<
if (n <= 3)
return [n]
Line 888 ⟶ 933:
ans.push(n)
return ans
}</
Examples:<
for i, p in prime_numbers(num)
output .= p " * "
MsgBox % num " = " Trim(output, " * ")
return</
{{out}}
<pre>8388607 = 47 * 178481</pre>
=={{header|AWK}}==
As the examples show, pretty large numbers can be factored in tolerable time:
<
function pfac(n, r, f){
r = ""; f = 2
Line 916 ⟶ 960:
# For each line of input, print the prime factors.
{ print pfac($1) }
</syntaxhighlight>
{{out}} entering input on stdin:
<pre>$
Line 927 ⟶ 971:
8796093022207
431 9719 2099863</pre>
=={{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
9050 FOR CA = 2 TO INT( SQR(I))
9060 IF I = 1 THEN RETURN
9070 IF INT(I / CA) * CA = I THEN GOSUB 9200 : GOTO 9060
9080 CA = CA + SC : SC = 1
9090 NEXT CA
9100 IF I = 1 THEN RETURN
9110 CA = I
9200 PF(0) = PF(0) + 1
9210 PF(PF(0)) = CA
9220 I = I / CA
9230 RETURN</syntaxhighlight>
==={{header|ASIC}}===
{{trans|XPL0}}
<syntaxhighlight lang="basic">
REM Prime decomposition
DIM Facs(14)
REM -(2^15) has most prime factors (15 twos) than other 16-bit signed integer.
PRINT "Enter a number";
INPUT N
GOSUB CalcFacs:
FacsCntM1 = FacsCnt - 1
FOR I = 0 TO FacsCntM1
PRINT Facs(I);
NEXT I
PRINT
END
CalcFacs:
N = ABS(N)
FacsCnt = 0
IF N >= 2 THEN
I = 2
SqrI = I * I
WHILE SqrI <= N
NModI = N MOD I
IF NModI = 0 THEN
N = N / I
Facs(FacsCnt) = I
FacsCnt = FacsCnt + 1
I = 2
ELSE
I = I + 1
ENDIF
SqrI = I * I
WEND
Facs(FacsCnt) = N
FacsCnt = FacsCnt + 1
ENDIF
RETURN
</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|Commodore BASIC}}===
{{works_with|Commodore BASIC|2.0}}
It's not easily possible to have arbitrary precision integers in PET basic, so here is at least a version using built-in data types (reals). On return from the subroutine starting at 9000 the global array pf contains the number of factors followed by the factors themselves:
<syntaxhighlight lang="zxbasic">9000 REM ----- function generate
9010 REM in ... i ... number
9020 REM out ... pf() ... factors
9030 REM mod ... ca ... pf candidate
9040 pf(0)=0 : ca=2 : REM special case
9050 IF i=1 THEN RETURN
9060 IF INT(i/ca)*ca=i THEN GOSUB 9200 : GOTO 9050
9070 FOR ca=3 TO INT( SQR(i)) STEP 2
9080 IF i=1 THEN RETURN
9090 IF INT(i/ca)*ca=i THEN GOSUB 9200 : GOTO 9080
9100 NEXT
9110 IF i>1 THEN ca=i : GOSUB 9200
9120 RETURN
9200 pf(0)=pf(0)+1
9210 pf(pf(0))=ca
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}}===
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64
Function isPrime(n As Integer) As Boolean
If n Mod 2 = 0 Then Return n = 2
If n Mod 3 = 0 Then Return n = 3
Dim d As Integer = 5
While d * d <= n
If n Mod d = 0 Then Return False
d += 2
If n Mod d = 0 Then Return False
d += 4
Wend
Return True
End Function
Sub getPrimeFactors(factors() As UInteger, n As UInteger)
If n < 2 Then Return
If isPrime(n) Then
Redim factors(0 To 0)
factors(0) = n
Return
End If
Dim factor As UInteger = 2
Do
If n Mod factor = 0 Then
Redim Preserve factors(0 To UBound(factors) + 1)
factors(UBound(factors)) = factor
n \= factor
If n = 1 Then Return
If isPrime(n) Then factor = n
Else
factor += 1
End If
Loop
End Sub
Dim factors() As UInteger
Dim primes(1 To 17) As UInteger = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59}
Dim n As UInteger
For i As UInteger = 1 To 17
Erase factors
n = 1 Shl primes(i) - 1
getPrimeFactors factors(), n
Print "2^";Str(primes(i)); Tab(5); " - 1 = "; Str(n); Tab(30);" => ";
For j As UInteger = LBound(factors) To UBound(factors)
Print factors(j);
If j < UBound(factors) Then Print " x ";
Next j
Print
Next i
Print
Print "Press any key to quit"
Sleep</syntaxhighlight>
{{out}}
<pre>
2^2 - 1 = 3 => 3
2^3 - 1 = 7 => 7
2^5 - 1 = 31 => 31
2^7 - 1 = 127 => 127
2^11 - 1 = 2047 => 23 x 89
2^13 - 1 = 8191 => 8191
2^17 - 1 = 131071 => 131071
2^19 - 1 = 524287 => 524287
2^23 - 1 = 8388607 => 47 x 178481
2^29 - 1 = 536870911 => 233 x 1103 x 2089
2^31 - 1 = 2147483647 => 2147483647
2^37 - 1 = 137438953471 => 223 x 616318177
2^41 - 1 = 2199023255551 => 13367 x 164511353
2^43 - 1 = 8796093022207 => 431 x 9719 x 2099863
2^47 - 1 = 140737488355327 => 2351 x 4513 x 13264529
2^53 - 1 = 9007199254740991 => 6361 x 69431 x 20394401
2^59 - 1 = 576460752303423487 => 179951 x 3203431780337
</pre>
==={{header|Palo Alto Tiny BASIC}}===
{{trans|Tiny BASIC|More structured composition is used (though created with <code>GOTO</code>s).}}
<syntaxhighlight lang="basic">
10 REM PRIME DECOMPOSITION
20 INPUT "ENTER A NUMBER"N
30 PRINT "--------------"
40 LET N=ABS(N)
50 IF N<2 STOP
60 LET I=2
70 IF I*I>N GOTO 150
80 LET M=N-(N/I)*I
90 IF M#0 GOTO 130
100 LET N=N/I
110 PRINT I
120 LET I=2
130 IF M#0 LET I=I+1
140 GOTO 70
150 PRINT N
160 STOP
</syntaxhighlight>
{{out}}
3 runs.
<pre>
ENTER A NUMBER:2520
--------------
2
2
2
3
3
5
7
</pre>
<pre>
ENTER A NUMBER:16384
--------------
2
2
2
2
2
2
2
2
2
2
2
2
2
2
</pre>
<pre>
ENTER A NUMBER:13
--------------
13
</pre>
==={{header|PureBasic}}===
{{works with|PureBasic|4.41}}
<syntaxhighlight lang="purebasic">
CompilerIf #PB_Compiler_Debugger
CompilerError "Turn off the debugger if you want reasonable speed in this example."
CompilerEndIf
Define.q
Procedure Factor(Number, List Factors())
Protected I = 3
While Number % 2 = 0
AddElement(Factors())
Factors() = 2
Number / 2
Wend
Protected Max = Number
While I <= Max And Number > 1
While Number % I = 0
AddElement(Factors())
Factors() = I
Number/I
Wend
I + 2
Wend
EndProcedure
Number = 9007199254740991
NewList Factors()
time = ElapsedMilliseconds()
Factor(Number, Factors())
time = ElapsedMilliseconds()-time
S.s = "Factored " + Str(Number) + " in " + StrD(time/1000, 2) + " seconds."
ForEach Factors()
S + #CRLF$ + Str(Factors())
Next
MessageRequester("", S)</syntaxhighlight>
{{out}}
<pre>Factored 9007199254740991 in 0.27 seconds.
6361
69431
20394401</pre>
==={{header|S-BASIC}}===
<syntaxhighlight lang="s-basic">
rem - return p mod q
function mod(p, q = integer) = integer
end = p - q * (p/q)
dim integer factors(16) rem log2(maxint) is sufficiently large
comment
Find the prime factors of n and store in global array factors
(arrays cannot be passed as parameters) and return the number
found. If n is prime, it will be stored as the only factor.
end
function primefactors(n = integer) = integer
var p, count = integer
p = 2
count = 1
while n >= (p * p) do
begin
if mod(n, p) = 0 then
begin
factors(count) = p
count = count + 1
n = n / p
end
else
p = p + 1
end
factors(count) = n
end = count
rem -- exercise the routine by checking odd numbers from 77 to 99
var i, k, nfound = integer
for i = 77 to 99 step 2
nfound = primefactors(i)
print i;"; ";
for k = 1 to nfound
print factors(k);
next k
print
next i
end
</syntaxhighlight>
{{out}}
<pre>
77: 7 11
79: 79
81: 3 3 3 3
83: 83
85: 5 17
87: 3 29
89: 89
91: 7 13
93: 3 31
95: 5 19
97: 97
99: 3 3 11
</pre>
==={{header|TI-83 BASIC}}===
<syntaxhighlight lang="ti83b">::prgmPREMIER
Disp "FACTEURS PREMIER"
Prompt N
If N<1:Stop
ClrList L1 ,L2
0→K
iPart(√(N))→L
N→M
For(I,2,L)
0→J
While fPart(M/I)=0
J+1→J
M/I→M
End
If J≠0
Then
K+1→K
I→L 1(K)
J→L2(K)
I→Z:prgmVSTR
" "+Str0→Str1
If J≠1
Then
J→Z:prgmVSTR
Str1+"^"+Str0→Str1
End
Disp Str1
End
If M=1:Stop
End
If M≠1
Then
If M≠N
Then
M→Z:prgmVSTR
" "+Str0→Str1
Disp Str1
Else
Disp "PREMIER"
End
End
::prgmVSTR
{Z,Z}→L5
{1,2}→L6
LinReg(ax+b)L6,L5,Y ₀
Equ►String(Y₀,Str0)
length(Str0)→O
sub(Str0,4,O-3)→Str0
ClrList L5,L6
DelVar Y </syntaxhighlight>
{{out}}
<pre>
FACTEURS PREMIER
N=?1047552
2^10
3
11
31
</pre>
==={{Header|Tiny BASIC}}===
{{works with|TinyBasic}}
<syntaxhighlight lang="basic">10 PRINT "Enter a number."
20 INPUT N
25 PRINT "------"
30 IF N<0 THEN LET N = -N
40 IF N<2 THEN END
50 LET I = 2
60 IF I*I > N THEN GOTO 200
70 IF (N/I)*I = N THEN GOTO 300
80 LET I = I + 1
90 GOTO 60
200 PRINT N
210 END
300 LET N = N / I
310 PRINT I
320 GOTO 50</syntaxhighlight>
{{out}}
<pre>
Enter a number.
32
------
2
2
2
2
2
Enter a number.
2520
------
2
2
2
3
3
5
7
Enter a number.
13
------
13
</pre>
==={{header|VBScript}}===
<syntaxhighlight lang="vb">Function PrimeFactors(n)
arrP = Split(ListPrimes(n)," ")
divnum = n
Do Until divnum = 1
'The -1 is to account for the null element of arrP
For i = 0 To UBound(arrP)-1
If divnum = 1 Then
Exit For
ElseIf divnum Mod arrP(i) = 0 Then
divnum = divnum/arrP(i)
PrimeFactors = PrimeFactors & arrP(i) & " "
End If
Next
Loop
End Function
Function IsPrime(n)
If n = 2 Then
IsPrime = True
ElseIf n <= 1 Or n Mod 2 = 0 Then
IsPrime = False
Else
IsPrime = True
For i = 3 To Int(Sqr(n)) Step 2
If n Mod i = 0 Then
IsPrime = False
Exit For
End If
Next
End If
End Function
Function ListPrimes(n)
ListPrimes = ""
For i = 1 To n
If IsPrime(i) Then
ListPrimes = ListPrimes & i & " "
End If
Next
End Function
WScript.StdOut.Write PrimeFactors(CInt(WScript.Arguments(0)))
WScript.StdOut.WriteLine</syntaxhighlight>
{{out}}
<pre>
C:\>cscript /nologo primefactors.vbs 12
2 3 2
C:\>cscript /nologo primefactors.vbs 50
2 5 5
</pre>
=={{header|Batch file}}==
Unfortunately Batch does'nt have a BigNum library so the maximum number that can be decomposed is 2^31-1
<
@echo off
::usage: cmd /k primefactor.cmd number
Line 956 ⟶ 1,637:
set/a compo/=div
goto:loopdiv
</syntaxhighlight>
=={{header|Befunge}}==
{{works_with|befungee}}
Handles safely integers only up to 250 (or ones which don't have prime divisors greater than 250).
<
> : 11g %!|
> 11g 1+ 11p v
^ <</
=={{header|BQN}}==
An efficient <code>Factor</code> function using trial division and Pollard's rho algorithm is given in bqn-libs [https://github.com/mlochbaum/bqn-libs/blob/master/primes.bqn primes.bqn]. The following standalone version is based on the trial division there, and builds in the sieve from [[Extensible prime generator#BQN|Extensible prime generator]].
<syntaxhighlight lang="bqn">Factor ← { 𝕊n:
# Prime sieve
primes ← ↕0
Sieve ← { p 𝕊 a‿b:
p(⍋↑⊣)↩√b ⋄ l←b-a
E ← {↕∘⌈⌾(((𝕩|-a)+𝕩×⊢)⁼)l} # Indices of multiples of 𝕩
a + / (1⥊˜l) E⊸{0¨⌾(𝕨⊸⊏)𝕩}´ p # Primes in segment [a,b)
}
# Factor by trial division
r ← ↕0 # Result list
Try ← {
m ← (1+⌊√n) ⌊ 2×𝕩 # Upper bound for factors this round
𝕩<m ? # Stop if no factors
primes ∾↩ np ← primes Sieve 𝕩‿m # New primes
{0=𝕩|n? r∾↩𝕩 ⋄ n÷↩𝕩 ⋄ 𝕊𝕩 ;@}¨ np # Try each one
𝕊 m # Next segment
;@}
Try 2
r ∾ 1⊸<⊸⥊n
}</syntaxhighlight>
{{out}}
<syntaxhighlight lang="bqn"> > ⋈⟜Factor¨ 1232123+↕4 # Some factored numbers
┌─
╵ 1232123 ⟨ 29 42487 ⟩
1232124 ⟨ 2 2 3 102677 ⟩
1232125 ⟨ 5 5 5 9857 ⟩
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}}==
<
blsq ) 12fC
{2 2 3}
</syntaxhighlight>
=={{header|C}}==
===Version 1===
Relatively sophiscated sieve method based on size 30 prime wheel. The code does not pretend to handle prime factors larger than 64 bits. All 32-bit primes are cached with 137MB data. Cache data takes about a minute to compute the first time the program is run, which is also saved to the current directory, and will be loaded in a second if needed again.
<
#include <stdio.h>
#include <stdlib.h>
Line 1,145 ⟶ 1,880:
return 0;
}</
===Using GNU Compiler Collection gcc extensions===
Line 1,157 ⟶ 1,892:
way, and in the case of this sample it requires the GCC "nested procedure"
extension to the C language.
<
#include <stdio.h>
#include <math.h>
Line 1,263 ⟶ 1,998:
CONTINUE;
}
}</
{{out}}
<pre>
Line 1,286 ⟶ 2,021:
Note: gcc took 487,719 BogoMI to complete the example.
To understand what was going on with the above code, pass it through <code>cpp</code> and read the outcome. Translated into normal C code sans the function call overhead, it's really this (the following uses a adjustable cache, although setting it beyond a few thousands doesn't gain further benefit):<
#include <stdlib.h>
#include <stdint.h>
Line 1,358 ⟶ 2,093:
return 0;
}</
===Version 2===
<syntaxhighlight lang="c">
typedef unsigned long long int ulong; // define a type that represent the limit (64-bit)
ulong mod_mul(ulong a, ulong b, const ulong mod) {
ulong res = 0, c; // return (a * b) % mod, avoiding overflow errors while doing modular multiplication.
for (b %= mod; a; a & 1 ? b >= mod - res ? res -= mod : 0, res += b : 0, a >>= 1, (c = b) >= mod - b ? c -= mod : 0, b += c);
return res % mod;
}
ulong mod_pow(ulong n, ulong exp, const ulong mod) {
ulong res = 1; // return (n ^ exp) % mod
for (n %= mod; exp; exp & 1 ? res = mod_mul(res, n, mod) : 0, n = mod_mul(n, n, mod), exp >>= 1);
return res;
}
ulong square_root(const ulong N) {
ulong res = 0, rem = N, c, d;
for (c = 1 << 62; c; c >>= 2) {
d = res + c;
res >>= 1;
if (rem >= d)
rem -= d, res += c;
} // returns the square root of N.
return res;
}
int is_prime(const ulong N) {
ulong i = 1; // return a truthy value about the primality of N.
if (N > 1) for (; i < 64 && mod_pow(i, N - 1, N) <= 1; ++i);
return i == 64;
}
ulong pollard_rho(const ulong N) {
// Require : N is a composite number, not a square.
// Ensure : res is a non-trivial factor of N.
// Option : change the timeout, change the rand function.
static const int timeout = 18;
static unsigned long long rand_val = 2994439072U;
rand_val = (rand_val * 1025416097U + 286824428U) % 4294967291LLU;
ulong res = 1, a, b, c, i = 0, j = 1, x = 1, y = 1 + rand_val % (N - 1);
for (; res == 1; ++i) {
if (i == j) {
if (j >> timeout)
break;
j <<= 1;
x = y;
}
a = y, b = y; // performs y = (y * y) % N
for (y = 0; a; a & 1 ? b >= N - y ? y -= N : 0, y += b : 0, a >>= 1, (c = b) >= N - b ? c -= N : 0, b += c);
y = (1 + y) % N;
for (a = y > x ? y - x : x - y, b = N; (a %= b) && (b %= a);); // compute the gcd(abs(y - x), N);
res = a | b;
}
return res;
}
void factor(const ulong N, ulong *array) {
// very basic manager that fill the given array (the size of the result is the first array element)
// it does not perform initial trial divisions, which is generally highly recommended.
if (N < 4 || is_prime(N)) {
if (N > 1 || !*array) array[++*array] = N;
return;
}
ulong x = square_root(N);
if (x * x != N) x = pollard_rho(N);
factor(x, array);
factor(N / x, array);
}
#include <stdio.h>
int main(void) {
// simple test.
unsigned long long n = 18446744073709551615U;
ulong fac[65] = {0};
factor(n, fac);
for (ulong i = 1; i <= *fac; ++i)
printf("* %llu\n", fac[i]);
}
</syntaxhighlight>
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
Line 1,404 ⟶ 2,223:
}
}
}</
===Simple trial division===
Line 1,410 ⟶ 2,229:
Although this three-line algorithm does not mention anything about primes, the fact that factors are taken out of the number <code>n</code> in ascending order garantees the list will only contain primes.
<
namespace PrimeDecomposition
Line 1,426 ⟶ 2,245:
return factors;
}
}</
=={{header|C++}}==
{{works with|g++|4.1.2 20061115 (prerelease) (Debian 4.1.1-21)}}
{{libheader|GMP}}
<
#include <gmpxx.h>
Line 1,515 ⟶ 2,334:
std::cout << "\n";
}
}</
=== Simple trial division ===
<
#include <iostream>
Line 1,552 ⟶ 2,371:
}
return 0;
}</
=={{header|Clojure}}==
<
(defn factors
"Return a list of factors of N."
Line 1,565 ⟶ 2,384:
(if (= 0 (rem n k))
(recur (quot n k) k (cons k acc))
(recur n (inc k) acc)))))</
=={{header|Common Lisp}}==
<
(defun factor (n)
"Return a list of factors of N."
Line 1,596 ⟶ 2,394:
for d = 2 then (if (evenp d) (+ d 1) (+ d 2)) do
(cond ((> d max-d) (return (list n))) ; n is prime
((zerop (rem n d)) (return (cons d (factor (truncate n d)))))))))</
<
(defun factor (n &optional (acc '()))
(when (> n 1) (loop with max-d = (isqrt n)
Line 1,608 ⟶ 2,406:
(list (caar acc) (1+ (cadar acc)))
(cdr acc))
(cons (list d 1) acc)))))))))</
=={{header|D}}==
<
Unqual!T[] decompose(T)(in T number) pure nothrow
Line 1,637 ⟶ 2,435:
decompose(16860167264933UL.BigInt * 179951).writeln;
decompose(2.BigInt ^^ 100_000).group.writeln;
}</
{{out}}
<pre>[2]
Line 1,654 ⟶ 2,452:
{{libheader| System.SysUtils}}
{{Trans|C#}}
<syntaxhighlight lang="delphi">
program Prime_decomposition;
Line 1,708 ⟶ 2,506:
write(v, ' ');
readln;
end.</
=={{header|E}}==
Line 1,714 ⟶ 2,512:
This example assumes a function <code>isPrime</code> and was tested with [[Primality by Trial Division#E|this one]]. It could use a self-referential implementation such as the Python task, but the original author of this example did not like the ordering dependency involved.
<
var primesCache := [2]
/** A collection of all prime numbers. */
Line 1,742 ⟶ 2,540:
}
return factors
}</
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
proc decompose num . primes[] .
primes[] = [ ]
t = 2
while t * t <= num
if num mod t = 0
primes[] &= t
num = num / t
else
t += 1
.
.
primes[] &= num
.
decompose 9007199254740991 r[]
print r[]
</syntaxhighlight>
=={{header|EchoLisp}}==
The built-in '''prime-factors''' function performs the task.
<
→ (2 2 2 2 2 2 2 2 2 2)
Line 1,755 ⟶ 2,572:
(prime-factors 100000000000000000037)
→ (31 821 66590107 59004541)</
=={{header|Eiffel}}==
Uses the feature prime from the Task Primality by Trial Devision in the contract to check if the Result contains only prime numbers.
<
PRIME_DECOMPOSITION
Line 1,797 ⟶ 2,614:
is_divisor: across Result as r all p \\ r.item = 0 end
is_prime: across Result as r all prime (r.item) end
end</
The test was done in an application class. (Similar as in other Eiffel examples (ex. Selectionsort).)
Line 1,809 ⟶ 2,626:
=={{header|Ela}}==
{{trans|F#}}
<
decompose_prime n = loop n 2I
Line 1,817 ⟶ 2,634:
| else = loop c (p + 1I)
decompose_prime 600851475143I</
{{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}}==
<
def decomposition(n), do: decomposition(n, 2, [])
Line 1,836 ⟶ 2,727:
Enum.each(mersenne, fn {n,m} ->
:io.format "~3s :~20w = ~s~n", ["M#{n}", m, Prime.decomposition(m) |> Enum.join(" x ")]
end)</
{{out}}
Line 1,859 ⟶ 2,750:
=={{header|Erlang}}==
<
factors(N) ->
Line 1,869 ⟶ 2,760:
factors(N div K,K, [K|Acc]);
factors(N,K,Acc) ->
factors(N,K+1,Acc).</
=={{header|ERRE}}==
{{trans|Commodore BASIC}}
<syntaxhighlight lang="erre">
PROGRAM DECOMPOSE
Line 1,922 ⟶ 2,814:
PRINT
END PROGRAM
</syntaxhighlight>
=={{header|Ezhil}}==
<syntaxhighlight lang="ezhil">
## இந்த நிரல் தரப்பட்ட எண்ணின் பகாஎண் கூறுகளைக் கண்டறியும்
Line 2,070 ⟶ 2,961:
பதிப்பி "நீங்கள் தந்த எண்ணின் பகா எண் கூறுகள் இவை: ", பகாஎண்கூறுகள்
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
<
let rec loop c p =
if c < (p * p) then [c]
Line 2,081 ⟶ 2,972:
loop n 2I
printfn "%A" (decompose_prime 600851475143I)</
{{out}}
<pre>[71; 839; 1471; 6857]</pre>
Line 2,087 ⟶ 2,978:
=={{header|Factor}}==
<code>factors</code> from the <code>math.primes.factors</code> vocabulary converts a number into a sequence of its prime divisors; the rest of the code prints this sequence.
<
27720 factors
[ number>string ] map
" " join print ;</
=={{header|FALSE}}==
<
27720d;! {2 2 2 3 3 5 7 11}</
=={{header|Forth}}==
<
2
begin 2dup dup * >=
Line 2,106 ⟶ 2,997:
then
repeat
drop . ;</
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
implicit none
Line 2,140 ⟶ 3,031:
end subroutine find_factors
end module PrimeDecompose</
<
use PrimeDecompose
implicit none
Line 2,158 ⟶ 3,049:
end do
end program Primes</
=={{header|Frink}}==
Frink has a built-in factoring function which uses wheel factoring, trial division, Pollard p-1 factoring, and Pollard rho factoring.
It also recognizes some special forms (e.g. Mersenne numbers) and handles them efficiently.
<
{{out}} (total process time including JVM startup = 1.515 s):
Line 2,250 ⟶ 3,066:
=={{header|GAP}}==
Built-in function :
<
# [ 193707721, 761838257287 ]</
Or using the [http://www.gap-system.org/Manuals/pkg/factint/doc/chap0.html FactInt] package :
<
# [ [ 193707721, 761838257287 ], [ ] ]</
=={{header|Go}}==
<
import (
Line 2,295 ⟶ 3,111:
fmt.Println(v, "->", Primes(big.NewInt(v)))
}
}</
{{out}}
<pre>2147483648 -> [2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2]
Line 2,308 ⟶ 3,124:
so it does not require an "isPrime-like function",
assumed or otherwise.
<
if (target == 1) return [1L]
Line 2,336 ⟶ 3,152:
}
primeFactors
}</
{{out|Test #1}}
<
{{out|Output #1}}
Line 2,378 ⟶ 3,194:
{{out|Test #2}}
<
(1..60).step(2).findAll(isPrime).each { println ([number:"2**${it}-1", value:2**it-1, primes:decomposePrimes(2**it-1)]) }</
{{out|Output #2}}
Line 2,404 ⟶ 3,220:
The task description hints at using the <code>isPrime</code> function from the [[Primality by trial division#Haskell|trial division]] task:
<
-- [2..n] >>= (\p-> [p|isPrime p]) >>= divs n
where
divs n p | rem n p == 0 = p : divs (quot n p) p
| otherwise = []</
but it is not very efficient, to put it mildly. Inlining and fusing gets us the progressively more optimized
<
import Data.List (unfoldr)
Line 2,421 ⟶ 3,237:
takeWhile ((<=n).(^2)) [d..] ++ [n|n>1], mod n x==0]) (2,n)
= unfoldr (\(ds,n) -> listToMaybe [(x, (dropWhile (< x) ds, div n x)) | n>1, x <-
takeWhile ((<=n).(^2)) ds ++ [n|n>1], mod n x==0]) (primesList,n)</
The library function <code>listToMaybe</code> gets at most one element from its list argument. The last variant can be written as the optimal
<
where
divs n ds@(d:t) | d*d > n = [n | n > 1]
| r == 0 = d : divs q ds
| otherwise = divs n t
where (q,r) = quotRem n d</
See [[Sieve of Eratosthenes]] or [[Primality by trial division]] for a source of primes to use with this function.
Line 2,450 ⟶ 3,266:
=={{header|Icon}} and {{header|Unicon}}==
<
factors := primedecomp(2^43-1) # a big int
end
Line 2,467 ⟶ 3,283:
end
link factors</
{{libheader|Icon Programming Library}} [http://www.cs.arizona.edu/icon/library/src/procs/factors.icn Uses genfactors and prime from factors]
Line 2,475 ⟶ 3,291:
=={{header|J}}==
<syntaxhighlight lang
{{out|Example use}}
<
2 2 3 307</
and, more elaborately:
<
340282366920938463463374607431768211455
q: _1+2^128x
3 5 17 257 641 65537 274177 6700417 67280421310721
*/ q: _1+2^128x
340282366920938463463374607431768211455</
=={{header|Java}}==
Line 2,494 ⟶ 3,310:
This is a version for arbitrary-precision integers
which assumes the existence of a function with the signature:
<
You will need to import java.util.List, java.util.LinkedList, and java.math.BigInteger.
<
List<BigInteger> ans = new LinkedList<BigInteger>();
//loop until we test the number itself or the number is 1
Line 2,507 ⟶ 3,323:
}
return ans;
}</
Alternate version, optimised to be faster.
<
public List<BigInteger> primeDecomp(BigInteger a) {
Line 2,541 ⟶ 3,357:
}
return result;
}</
Another alternate version designed to make fewer modular calculations:
<
private static final BigInteger TWO = BigInteger.valueOf(2);
private static final BigInteger THREE = BigInteger.valueOf(3);
Line 2,588 ⟶ 3,404:
return factors;
}
</syntaxhighlight>
{{trans|C#}}
Simple but very inefficient method,
because it will test divisibility of all numbers from 2 to max prime factor.
When decomposing a large prime number this will take O(n) trial divisions instead of more common O(log n).
<
List<BigInteger> ans = new LinkedList<BigInteger>();
Line 2,603 ⟶ 3,419:
}
return ans;
}</
=={{header|JavaScript}}==
This code uses the BigInteger Library [http://xenon.stanford.edu/~tjw/jsbn/jsbn.js jsbn] and [http://xenon.stanford.edu/~tjw/jsbn/jsbn2.js jsbn2]
<
var n = new BigInteger(input.value, 10);
var TWO = new BigInteger("2", 10);
Line 2,645 ⟶ 3,461:
divisor = divisor.add(TWO);
}
}</
Without any library.
<
if (n <= 3)
return [n];
Line 2,687 ⟶ 3,503:
ans.push(n);
return ans;
}</
TDD using Jasmine
PrimeFactors.js
<
if (!n || n < 2)
return [];
Line 2,706 ⟶ 3,522:
return f;
};
</syntaxhighlight>
SpecPrimeFactors.js (with tag for Chutzpah)
<
describe("Prime Factors", function() {
Line 2,757 ⟶ 3,573:
});
});
</syntaxhighlight>
=={{header|jq}}==
{{works with|jq|1.
'''Works with gojq, the Go implementation of jq'''
The implementation is compact, fast and
no space is required to store the primes or factors already computed,
there is no reliance on an "is_prime" function, and square roots are only computed if needed.
Line 2,772 ⟶ 3,589:
valid is a flag, and sqrt is either null or the square root of n.
gojq supports unlimited-precision integer arithmetic, but the C implementation of jq
reliable for integers up to and including 9,007,199,254,740,992 (2^53). However, "factors"
could be easily modified to work with a "BigInt" library for jq, such as [https://gist.github.com/pkoppstein/d06a123f30c033195841 BigInt.jq].
<
. as $in
| [2, $in, false]
| recurse(
. as
| if $q == 1
elif $q
elif $p == 2
| if .[2] then .[0] else empty end ;</
'''Examples''':
<syntaxhighlight lang="jq">
24 | factors
#=> 2 2 2 3
[9007199254740992 | factors] | length
#=> 53
# 2**29-1
[ 536870911 | factors ]
#=> [233,1103,2089]</syntaxhighlight>
=={{header|Julia}}==
using package Primes.jl:
<
julia> Pkg.add("Primes")
julia> factor(8796093022207)
[9719=>1,431=>1,2099863=>1]
</syntaxhighlight>
(The <code>factor</code> function returns a dictionary
whose keys are the factors and whose values are the multiplicity of each factor.)
=={{header|Kotlin}}==
<
import java.math.BigInteger
Line 2,844 ⟶ 3,664:
println("2^${"%2d".format(prime)} - 1 = ${bigPow2.toString().padEnd(30)} => ${getPrimeFactors(bigPow2)}")
}
}</
{{out}}
Line 2,876 ⟶ 3,696:
=={{header|Lambdatalk}}==
<
{def prime_fact.smallest
{def prime_fact.smallest.r
Line 2,908 ⟶ 3,728:
86:[2,43] 87:[3,29] 88:[2,2,2,11] 89:[89] 90:[2,3,3,5] 91:[7,13] 92:[2,2,23] 93:[3,31] 94:[2,47] 95:[5,19] 96:[2,2,2,2,2,3]
97:[97] 98:[2,7,7] 99:[3,3,11] 100:[2,2,5,5] 101:[101]
</syntaxhighlight>
=={{header|LFE}}==
<
(defun factors (n)
(factors n 2 '()))
Line 2,923 ⟶ 3,743:
((n k acc)
(factors n (+ k 1) acc)))
</syntaxhighlight>
=={{header|Lingo}}==
<
-- To overcome the limits of integers (signed 32-bit in Lingo),
-- the number can be specified as float (which works up to 2^53).
Line 2,948 ⟶ 3,768:
f.add(n)
return f
end</
<
-- [2.0000, 2.0000, 3.0000]
Line 2,959 ⟶ 3,779:
put getPrimeFactors(1125899906842623.0)
-- [3, 251, 601, 4051, 614141]</
=={{header|Logo}}==
<
if :p*:p > :n [output (list :n)]
if less? 0 modulo :n :p [output (decompose :n bitor 1 :p+1)]
output fput :p (decompose :n/:p :p)
end</
=={{header|Lua}}==
Line 2,972 ⟶ 3,792:
is located at [[Primality by trial division#Lua]]
<
local f = {}
Line 2,993 ⟶ 3,813:
return f
end</
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module Prime_decomposition {
Inventory Known1=2@, 3@
Line 3,047 ⟶ 3,867:
}
Prime_decomposition
</syntaxhighlight>
=={{header|Maple}}==
Line 3,055 ⟶ 3,875:
of prime factors and their multiplicities:
<
(7) (191)
</syntaxhighlight>
<
[1, [[7, 1], [191, 1]]]
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Bare built-in function does:
<
Read as: 2 to the power 5 times 3 squared times 7 (to the power 1).
To show them nicely we could use the following functions:
<
ShowPrimeDecomposition[input_Integer]:=Print@@{input," = ",Sequence@@Riffle[supscript@@@FactorInteger[input]," "]}</
Example for small prime:
<syntaxhighlight lang
gives:
<
Examples for large primes:
<
gives back:
<
0.000231 sec
1152921504606846975 = 3^2 5^2 7 11 13 31 41 61 151 331 1321
Line 3,100 ⟶ 3,920:
0.009419 sec
1427247692705959881058285969449495136382746623 = 3^2 7 11 31 151 251 331 601 1801 4051 100801 10567201 1133836730401
0.007705 sec</
=={{header|MATLAB}}==
<
outputPrimeDecomposition = factor(inputValue);</
=={{header|Maxima}}==
Using the built-in function:
<
(%i2) factor(2016);
(%o2) 2^5*3^2*7
</syntaxhighlight>
Using the underlying language:
<
/* or, slighlty more "functional" */
Line 3,119 ⟶ 3,939:
prime_dec(2^4*3^5*5*7^2);
/* [2, 2, 2, 2, 3, 3, 3, 3, 3, 5, 7, 7] */</
=={{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}}==
<
SET HI=HI\1
KILL ERATO1 ;Don't make it new - we want it to remain after the quit
Line 3,143 ⟶ 4,037:
IF I>1 SET PRIMDECO=$S($L(PRIMDECO)>0:PRIMDECO_"^",1:"")_I D PRIMDECO(N/I)
;that is, if I is a factor of N, add it to the string
QUIT</
{{out|Usage}}
<pre>USER>K ERATO1,PRIMDECO D PRIMDECO^ROSETTA(31415) W PRIMDECO
Line 3,160 ⟶ 4,054:
=={{header|Nim}}==
Based on python floating point solution, but using integers rather than floats.
<
proc getStep(n: int64): int64 {.inline.} =
Line 3,197 ⟶ 4,091:
let start = cpuTime()
stdout.write primeFac(p).join(", ")
echo &" => {(1000 * (cpuTime() - start)).toInt} ms"</
{{out}}
Line 3,220 ⟶ 4,114:
=={{header|OCaml}}==
<
let prime_decomposition x =
Line 3,231 ⟶ 4,125:
inner (succ_big_int c) p
in
inner (succ_big_int (succ_big_int zero_big_int)) x;;</
=={{header|Octave}}==
<
=={{header|Oforth}}==
Line 3,240 ⟶ 4,134:
Oforth handles aribitrary precision integers.
<
| k p |
ListBuffer new
Line 3,253 ⟶ 4,147:
]
n 1 > ifTrue: [ n over add ]
dup freeze ;</
{{out}}
Line 3,269 ⟶ 4,163:
Thus <code>factor(12)==[2,2;3,1]</code> is true.
But it's simple enough to convert this to a vector with repetition:
<
my(f=factor(n),v=f[,1]~);
for(i=1,#v,
Line 3,277 ⟶ 4,171:
);
vecsort(v)
};</
=={{header|Pascal}}==
<
type
Line 3,317 ⟶ 4,211:
for j := low(factors) to high(factors) do
writeln (factors[j]);
end.</
{{out}}
<pre>% ./PrimeDecomposition
Line 3,336 ⟶ 4,230:
'''Optimization:'''
<
type
Line 3,381 ⟶ 4,275:
writeln (factors[j]);
readln;
end.</
=={{header|Perl}}==
Line 3,388 ⟶ 4,282:
===Trivial trial division (very slow)===
<
my ($n, $d, @out) = (shift, 1);
while ($n > 1 && $d++) {
Line 3,396 ⟶ 4,290:
}
print "@{[prime_factors(1001)]}\n";</
===Better trial division===
This is ''much'' faster than the trivial version above.
<
my($n, $p, @out) = (shift, 3);
return if $n < 1;
Line 3,413 ⟶ 4,307:
push @out, $n if $n > 1;
@out;
}</
===Modules===
Line 3,419 ⟶ 4,313:
These both take about 1 second to factor all Mersenne numbers from M_1 to M_150.
{{libheader|ntheory}}
<
use bigint;
Line 3,425 ⟶ 4,319:
my $p = 2 ** $_ - 1;
print "2**$_-1: ", join(" ", factor($p)), "\n";
} 100, 150;</
{{out}}
<pre>
Line 3,441 ⟶ 4,335:
{{libheader|Math::Pari}}
<
# Convert Math::Pari's format into simple vector
Line 3,453 ⟶ 4,347:
my $p = 2 ** $_ - 1;
print "2^$_-1: ", join(" ", factor($p)), "\n";
}</
With the same output.
Line 3,459 ⟶ 4,353:
For small numbers less than 2<small><sup>53</sup></small> on 32bit and 2<small><sup>64</sup></small> on 64bit just use prime_factors().
{{libheader|Phix/mpfr}}
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.0"</span><span style="color: #0000FF;">)</span>
Line 3,474 ⟶ 4,368:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"2^%d-1 = %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zs</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #
<span style="color: #7060A8;">mpz_set_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s = %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_factorstring</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_pollard_rho</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">))})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 3,511 ⟶ 4,403:
600851475143 = 71*839*1471*6857
100000000000000000037 = 31*821*59004541*66590107
"
</pre>
=={{header|Picat}}==
<syntaxhighlight lang="picat">go =>
% Checking 2**prime-1
foreach(P in primes(60))
Factors = factors(2**P-1),
println([n=2**P-1,factors=Factors])
end,
nl,
% Testing a larger number
println(factors(1361129467683753853853498429727072845823)),
nl.
%
% factors of N
%
factors(N) = Factors =>
Factors = [],
M = N,
while (M mod 2 == 0)
Factors := Factors ++ [2],
M := M div 2
end,
T = 3,
while (M > 1, T < 1+(sqrt(M)))
if M mod T == 0 then
[Divisors, NewM] = alldivisorsM(M, T),
Factors := Factors ++ Divisors,
M := NewM
end,
T := T + 2
end,
if M > 1 then Factors := Factors ++ [M] end.
alldivisorsM(N,Div) = [Divisors,M] =>
M = N,
Divisors = [],
while (M mod Div == 0)
Divisors := Divisors ++ [Div],
M := M div Div
end.</syntaxhighlight>
{{out}}
<pre>[n = 3,factors = [3]]
[n = 7,factors = [7]]
[n = 31,factors = [31]]
[n = 127,factors = [127]]
[n = 2047,factors = [23,89]]
[n = 8191,factors = [8191]]
[n = 131071,factors = [131071]]
[n = 524287,factors = [524287]]
[n = 8388607,factors = [47,178481]]
[n = 536870911,factors = [233,1103,2089]]
[n = 2147483647,factors = [2147483647]]
[n = 137438953471,factors = [223,616318177]]
[n = 2199023255551,factors = [13367,164511353]]
[n = 8796093022207,factors = [431,9719,2099863]]
[n = 140737488355327,factors = [2351,4513,13264529]]
[n = 9007199254740991,factors = [6361,69431,20394401]]
[n = 576460752303423487,factors = [179951,3203431780337]]
[3,11,31,131,2731,8191,409891,7623851,145295143558111]</pre>
=={{header|PicoLisp}}==
Line 3,518 ⟶ 4,472:
17 19 23 29 31 37 ..), as described by Donald E. Knuth, "The Art of Computer
Programming", Vol.2, p.365.
<
(make
(let (D 2 L (1 2 2 . (4 2 4 2 4 6 2 6 .)) M (sqrt N))
Line 3,527 ⟶ 4,481:
(link N) ) ) )
(factor 1361129467683753853853498429727072845823)</
{{out}}
<pre>-> (3 11 31 131 2731 8191 409891 7623851 145295143558111)</pre>
=={{header|PL/0}}==
{{trans|Tiny BASIC}}
The overlapping loops, created with <code>GOTO</code>s in the original version, have been replaced with structures with single entries and single exits (like in structured programming).
The program waits for a number, and then displays the prime factors of the number.
<syntaxhighlight lang="pascal">
var i, n, nmodi;
begin
? n;
if n < 0 then n := -n;
if n >= 2 then
begin
i := 2;
while i * i <= n do
begin
nmodi := n - (n / i) * i;
if nmodi = 0 then
begin
n := n / i;
! i;
i := 2
end;
if nmodi <> 0 then
i := i + 1
end;
! n
end;
end.
</syntaxhighlight>
3 runs.
{{in}}
<pre>2520</pre>
{{out}}
<pre>
2
2
2
3
3
5
7
</pre>
{{in}}
<pre>16384</pre>
{{out}}
<pre>
2
2
2
2
2
2
2
2
2
2
2
2
2
2
</pre>
{{in}}
<pre>13</pre>
{{out}}
<pre>
13
</pre>
=={{header|PL/I}}==
<
test: procedure options (main, reorder);
declare (n, i) fixed binary (31);
Line 3,570 ⟶ 4,592:
end test;
</syntaxhighlight>
{{out|Results from various runs}}
<pre>
Line 3,583 ⟶ 4,605:
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
function eratosthenes ($n) {
if($n -gt 1){
Line 3,614 ⟶ 4,636:
$prime
}
"$(prime-decomposition
"$(prime-decomposition
</syntaxhighlight>
<b>Output:</b>
<pre>
Line 3,622 ⟶ 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}}==
<
SN is sqrt(N),
prime_decomp_1(N, SN, 2, [], L).
Line 3,660 ⟶ 4,702:
prime_decomp_2(N, SN, D1, L, LF)
)
).</
{{out}}
<
% 138,882 inferences, 0.344 CPU in 0.357 seconds (96% CPU, 404020 Lips)
L = [20394401,69431,6361].
Line 3,673 ⟶ 4,715:
?- time(prime_decomp(1361129467683753853853498429727072845823, L)).
% 18,080,807 inferences, 7.953 CPU in 7.973 seconds (100% CPU, 2273422 Lips)
L = [145295143558111,7623851,409891,8191,2731,131,31,11,3].</
====Simple version====
Line 3,679 ⟶ 4,721:
Optimized to stop on square root, and count by +2 on odds, above 2.
<
factors2( N, FS).
Line 3,694 ⟶ 4,736:
; 0 is N rem K -> FS = [K|FS2], N2 is N div K, factors( N2, K, FS2)
; K2 is K+2, factors( N, K2, FS)
).</
====Expression Tree version====
Uses a 2*3*5*7 factor wheel, but the main feature is that it returns the decomposition as a fully simplified expression tree.
<syntaxhighlight lang="prolog">
wheel2357(L) :-
W = [2, 4, 2, 4, 6, 2, 6, 4,
Line 3,734 ⟶ 4,776:
reverse_factors(A*B, C*A) :- reverse_factors(B, C), !.
reverse_factors(A, A).
</syntaxhighlight>
{{Out}}
<pre>
Line 3,757 ⟶ 4,799:
=={{header|Pure}}==
<
factor k n = k : factor k (n div k) if n mod k == 0;
= if n>1 then [n] else [] if k*k>n;
= factor (k+1) n if k==2;
= factor (k+2) n otherwise;
end;</
=={{header|Python}}==
===Python: Using Croft Spiral sieve===
Note: the program below is saved to file <code>prime_decomposition.py</code> and imported as a library [[Least_common_multiple#Python|here]], [[Semiprime#Python|here]], [[Almost_prime#Python|here]], [[Emirp primes#Python|here]] and [[Extensible_prime_generator#Python|here]].
<
import sys
from itertools import
def is_prime(n):
return list(zip((True, False), decompose(n)))[-1][0]
class IsPrimeCached(dict):
def __missing__(self, n):
Line 3,833 ⟶ 4,823:
self[n] = r
return r
is_prime_cached = IsPrimeCached()
def croft():
"""Yield prime integers using the Croft Spiral sieve.
Line 3,851 ⟶ 4,841:
for p in (2, 3, 5):
yield p
roots = {
q = 1
for
q +=
# Using dict membership testing instead of pop gives a
# 5-10% speedup over the first three million primes.
if q in roots:
p = roots
while not_primeroot[x
roots[x] = p
else:
roots[q * q] = q + q
yield q
primes = croft
def decompose(n):
for p in primes():
Line 3,886 ⟶ 4,872:
if __name__ == '__main__':
# Example: calculate factors of Mersenne numbers to M59 #
import time
for m in primes():
p = 2 ** m - 1
Line 3,896 ⟶ 4,882:
print(factor, end=' ')
sys.stdout.flush()
print( "=> {0:.2f}s".format( time.time()-start ) )
if m >= 59:
break</
{{out}}
<pre>2**2-1 = 3, with factors:
Line 3,939 ⟶ 4,925:
Here a shorter and marginally faster algorithm:
<
try:
long
Line 3,960 ⟶ 4,946:
tocalc = 2**59-1
print("%s = %s" % (tocalc, fac(tocalc)))
print("Needed %ss" % (time.time() - start))</
{{out}}
Line 3,968 ⟶ 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 3,977 ⟶ 4,969:
drop
dup 1 = if conclude ]
drop ] is primefactors ( n --> [ )</syntaxhighlight>
{{out}}
Line 3,986 ⟶ 4,976:
=={{header|R}}==
<
x <- NULL
firstprime<- 2; secondprime <- 3; everyprime <- num
Line 4,000 ⟶ 4,990:
}
print(findfactors(1027*4))</
Or a more explicit (but less efficient) recursive approach:
===Recursive Approach (Less efficient for large numbers)===
<syntaxhighlight lang="r">
primes <- as.integer(c())
Line 4,041 ⟶ 5,031:
}
}
</syntaxhighlight>
=== Alternate solution ===
<
a <- NULL
if (n > 1) {
Line 4,061 ⟶ 5,051:
}
a
}</
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
(require math)
(define (factors n)
(append-map (λ (x) (make-list (cadr x) (car x))) (factorize n)))
</syntaxhighlight>
Or, an explicit (and less efficient) computation:
<syntaxhighlight lang="racket">
#lang racket
(define (factors number)
Line 4,080 ⟶ 5,070:
(let-values ([(q r) (quotient/remainder n i)])
(if (zero? r) (cons i (loop q i)) (loop n (add1 i)))))))
</syntaxhighlight>
=={{header|Raku}}==
Line 4,087 ⟶ 5,077:
This is a pure Raku version that uses no outside libraries. It uses a variant of Pollard's rho factoring algorithm and is fairly performent when factoring numbers < 2⁸⁰; typically taking well under a second on an i7. It starts to slow down with larger numbers, but really bogs down factoring numbers that have more than 1 factor larger than about 2⁴⁰.
<syntaxhighlight lang="raku"
return $n if $n.is-prime;
return () if $n == 1;
Line 4,123 ⟶ 5,113:
"factors of $n: ",
prime-factors($n).join(' × '), " \t in ", (now - $start).fmt("%0.3f"), " sec."
}</
{{out}}
Line 4,139 ⟶ 5,129:
===External library===
If you really need a speed boost, load the highly optimized Perl 5 ntheory module. It needs a little extra plumbing to deal with the lack of built-in big integer support, but for large number factoring the interface overhead is worth it.
<syntaxhighlight lang="raku"
my $p5 = Inline::Perl5.new();
$p5.use( 'ntheory' );
Line 4,154 ⟶ 5,144:
say "factors of $n: ",
prime-factors($n).join(' × '), " \t in ", (now - $start).fmt("%0.3f"), " sec."
}</
{{out}}
<pre>factors of 536870911: 233 × 1103 × 2089 in 0.001 sec.
Line 4,178 ⟶ 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"></syntaxhighlight>
/*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,228 ⟶ 5,258:
<pre style="font-size:75%;height:160ex">
1 (0) prime factors: {unity}
2 (1) prime factors: [prime] 2
Line 4,354 ⟶ 5,385:
<pre style="font-size:75%>
3 (1) prime factors: [prime] 3
7 (1) prime factors: [prime] 7
Line 4,366 ⟶ 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 4,430 ⟶ 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 4,469 ⟶ 5,501:
===optimized more===
This REXX version is about '''20%''' faster than the 1<sup>st</sup> REXX version when factoring one million numbers.
<
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>
=={{header|Ring}}==
<
prime = 18705
decomp(prime)
Line 4,541 ⟶ 5,606:
next
return 1
</syntaxhighlight>
=={{header|RPL}}==
≪ { } SWAP DUP √ CEIL → lim
≪ 2
'''WHILE''' OVER 1 > OVER lim ≤ AND '''REPEAT'''
DUP2 /
'''IF''' DUP FP
'''THEN''' DROP DUP 2 ≠ + 1 +
'''ELSE''' SWAP ROT DROP ROT OVER + ROT ROT '''END'''
'''END''' DROP
'''IF''' DUP 1 ≠ '''THEN''' + '''ELSE''' DROP '''END'''
≫ ≫ ‘'''PDIV'''’ 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
#1048 '''PDIVB'''
{{out}}
<pre>
1: { #2d #2d #2d #131d }
</pre>
=={{header|Ruby}}==
===Built in===
<
=> true
irb(main):003:0> 2543821448263974486045199.prime_division
=> [[701, 1], [1123, 2], [2411, 1], [1092461, 2]]</
===Simple algorithm===
<
# This routine is terribly inefficient, but elegance rules.
def prime_factors(i)
Line 4,563 ⟶ 5,662:
factors = prime_factors(2**i-1)
puts "2**#{i}-1 = #{2**i-1} = #{factors.join(' * ')}"
end</
{{out}}
<pre>...
Line 4,572 ⟶ 5,671:
===Faster algorithm===
<
# This routine is more efficient than prime_factors,
# and quite similar to Integer#prime_division of MRI 1.9.
Line 4,603 ⟶ 5,702:
factors = prime_factors_faster(2**i-1)
puts "2**#{i}-1 = #{2**i-1} = #{factors.join(' * ')}"
end</
{{out}}
<pre>...
Line 4,613 ⟶ 5,712:
This benchmark compares the different implementations.
<
require 'mathn'
Benchmark.bm(24) do |x|
Line 4,622 ⟶ 5,721:
x.report(" Integer#prime_division") { i.prime_division }
end
end</
With [[MRI]] 1.8, ''prime_factors'' is slow, ''Integer#prime_division'' is fast, and ''prime_factors_faster'' is very fast. With MRI 1.9, Integer#prime_division is also very fast.
Line 4,644 ⟶ 5,743:
The implementation:
<
use num_traits::{One, Zero};
use std::fmt::{Display, Formatter};
Line 4,736 ⟶ 5,835:
}
}
</syntaxhighlight>
=={{header|Scala}}==
{{libheader|Scala}}
<
import collection.parallel.mutable.ParSeq
Line 4,845 ⟶ 5,881:
}
}
}</
{{out}}
<pre>
Line 4,868 ⟶ 5,904:
Since the problems seems to ask for it, here is one version that does it:
<
val zero = BigInt(0)
val one = BigInt(1)
Line 4,900 ⟶ 5,936:
def hasNext = currentN != one && currentN > zero
}</
The method isProbablePrime(n) has a chance of 1 - 1/(2^n) of correctly
Line 4,906 ⟶ 5,942:
Next is a version that does not depend on identifying primes,
and works with arbitrary integral numbers:
<
import num._
val two = one + one
Line 4,930 ⟶ 5,966:
def hasNext = currentN != one && currentN > zero
}</
{{out}}
Both versions can be rather slow, as they accept arbitrarily big numbers,
Line 4,959 ⟶ 5,995:
Alternatively, Scala LazyLists and Iterators support quite elegant one-line encodings of iterative/recursive algorithms, allowing us to to define the prime factorization like so:
<
import spire.implicits._
def pFactors(num: SafeLong): Vector[SafeLong] = Iterator.iterate((Vector[SafeLong](), num, SafeLong(2))){case (ac, n, f) => if(n%f == 0) (ac :+ f, n/f, f) else (ac, n, f + 1)}.dropWhile(_._2 != 1).next._1</
=={{header|Scheme}}==
<
(define (*factor divisor number)
(if (> (* divisor divisor) number)
Line 4,974 ⟶ 6,010:
(display (factor 111111111111))
(newline)</
{{out}}
(3 7 11 13 37 101 9901)
=={{header|Seed7}}==
<
result
var array integer: result is 0 times 0;
Line 4,996 ⟶ 6,032:
result &:= [](number);
end if;
end func;</
Original source: [http://seed7.sourceforge.net/algorith/math.htm#factorise]
Line 5,003 ⟶ 6,039:
'''Recursive Using isPrime'''
<
primeFactorization(num) := primeFactorizationHelp(num, []);
Line 5,013 ⟶ 6,049:
current when size(primeFactors) = 0
else
primeFactorizationHelp(num / product(primeFactors), current ++ primeFactors);</
Using isPrime Based On: [https://www.youtube.com/watch?v=CsCBkPg1FbE]
Line 5,019 ⟶ 6,055:
'''Recursive Trial Division'''
<
primeFactorizationHelp(num, divisor, factors(1)) :=
Line 5,026 ⟶ 6,062:
primeFactorizationHelp(num, divisor + 1, factors) when num mod divisor /= 0
else
primeFactorizationHelp(num / divisor, divisor, factors ++ [divisor]);</
=={{header|Sidef}}==
Built-in:
<
say factor_exp(536870911) #=> [[233, 1], [1103, 1], [2089, 1]]</
Trial division:
<
return [] if (n < 1)
gather {
Line 5,051 ⟶ 6,087:
take(n) if (n > 1)
}
}</
Calling the function:
<
=={{header|Simula}}==
Simula has no built-in function to test for prime numbers.<br>
Code for class bignum can be found here: https://rosettacode.org/wiki/Pi#Simula
<
EXTERNAL CLASS BIGNUM;
BIGNUM
Line 5,074 ⟶ 6,110:
REF(TEXTARRAY) NEWARR;
INTEGER I;
NEWARR :- NEW TEXTARRAY(
FOR I := 1 STEP 1 UNTIL SIZE DO BEGIN
NEWARR.DATA(I) :- ARR.DATA(I);
Line 5,140 ⟶ 6,176:
END;
</syntaxhighlight>
{{out}}
<pre>
Line 5,153 ⟶ 6,189:
=={{header|Slate}}==
Admittedly, this is just based on the Smalltalk entry below:
<
"Decomposes the Integer into primes, applying the block to each (in increasing
order)."
Line 5,167 ⟶ 6,203:
[div: next.
next: next + 2] "Just look at the next odd integer."
].</
=={{header|Smalltalk}}==
<
primesDo: aBlock [
| div next rest |
Line 5,184 ⟶ 6,220:
]
]
123456 primesDo: [ :each | each printNl ]</
=={{header|SPAD}}==
{{works with|FriCAS, OpenAxiom, Axiom}}
<syntaxhighlight lang="spad">
(1) -> factor 102400
Line 5,200 ⟶ 6,236:
Type: Factored(Integer)
</syntaxhighlight>
Domain:[http://fricas.github.io/api/Factored.html?highlight=factor Factored(R)]
Line 5,206 ⟶ 6,242:
=={{header|Standard ML}}==
Trial division
<syntaxhighlight lang="sml">
val factor = fn n :IntInf.int =>
let
Line 5,228 ⟶ 6,264:
end;
</syntaxhighlight>
<pre>
- Array.fromList(factor 122489234920000001278234798233);;
Line 5,238 ⟶ 6,274:
The following Mata function will factor any representable positive integer (that is, between 1 and 2^53).
<
n = n_
a = J(0,2,.)
Line 5,263 ⟶ 6,299:
return(a)
}
}</
=={{header|Swift}}==
Line 5,270 ⟶ 6,306:
Uses the sieve of Eratosthenes. This is generic on any type that conforms to BinaryInteger. So in theory any BigInteger library should work with it.
<
guard n > 2 else { return [] }
Line 5,294 ⟶ 6,330:
print("2^\(prime) - 1 = \(m) => \(decom)")
}</
{{out}}
Line 5,316 ⟶ 6,352:
=={{header|Tcl}}==
<
# list the prime factors of x in ascending order
set result [list]
Line 5,332 ⟶ 6,368:
return $result
}
</syntaxhighlight>
Testing
<
set n [expr {2**$m - 1}]
catch {time {set primes [factors $n]} 1} tm
puts [format "2**%02d-1 = %-18s = %-22s => %s" $m $n [join $primes *] $tm]
}</
{{out}}
<pre>2**02-1 = 3 = 3 => 184 microseconds per iteration
Line 5,358 ⟶ 6,394:
2**59-1 = 576460752303423487 = 179951*3203431780337 => 316009 microseconds per iteration</pre>
=={{header|TXR}}==
{{trans|Common Lisp}}
<syntaxhighlight lang="txr">@(next :args)
@(do
(defun factor (n)
Line 5,482 ⟶ 6,412:
@(output)
@num -> {@(rep)@factors, @(last)@factors@(end)}
@(end)</
{{out}}
<pre>$ txr factor.txr 1139423842450982345
Line 5,505 ⟶ 6,435:
=={{header|V}}==
like in scheme (using variables)
<
[inner [c p] let
[c c * p >]
Line 5,514 ⟶ 6,444:
ifte]
ifte].
2 swap inner].</
(mostly) the same thing using stack (with out variables)
<
[inner
[dup * <]
Line 5,526 ⟶ 6,456:
ifte]
ifte].
2 inner].</
Using it
<syntaxhighlight lang
=[3 11 37]
=={{header|Wren}}==
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Fmt
var vals = [1 << 31, 1234567, 333333, 987653, 2 * 3 * 5 * 7 * 11 * 13 * 17]
for (val in vals) {
Fmt.print("$10d -> $n", val,
}</
{{out}}
Line 5,640 ⟶ 6,483:
</pre>
=={{header|XPL0}}==
{{trans|PL/0|The algorithm itself is translated, but procedure which calculates factors and fills the result array is added.}}
{{works with|EXPL-32}}
<syntaxhighlight lang="xpl0">
\ Prime decomposition
code Abs=0, Rem=2, CrLf=9, IntIn=10, IntOut=11, Text=12;
define MaxFacIndex = 30;
\ -(2^31) has most prime factors (31 twos) than other 32-bit signed integer.
integer I, N, Facs(MaxFacIndex), FacsCnt;
procedure CalcFacs(N, Facs, FacsCnt);
integer N, Facs, FacsCnt;
integer I, Cnt;
begin
N:= Abs(N);
Cnt:=0;
if N >= 2 then
begin
I:= 2;
while I * I <= N do
begin
if Rem(N / I) = 0 then
begin
N:= N / I;
Facs(Cnt):= I; Cnt:= Cnt + 1;
I:= 2
end
else
I:= I + 1
end;
Facs(Cnt):= N; Cnt:= Cnt + 1
end;
FacsCnt(0):= Cnt
end;
begin
Text(0, "Enter a number: "); N:= IntIn(0);
CalcFacs(N, Facs, addr FacsCnt);
for I:= 0 to FacsCnt - 2 do
begin
IntOut(0, Facs(I)); Text(0, " ")
end;
IntOut(0, Facs(FacsCnt - 1)); CrLf(0)
end
</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|XSLT}}==
Let's assume that in XSLT the application of a template is similar to the invocation of a function. So when the following template
<
<xsl:template match="/numbers">
Line 5,714 ⟶ 6,616:
</xsl:template>
</xsl:stylesheet></
is applied against the document
<
<number><value>1</value></number>
<number><value>2</value></number>
Line 5,723 ⟶ 6,625:
<number><value>9</value></number>
<number><value>255</value></number>
</numbers></
then the output contains the prime decomposition of each number:
<
<body>
<ul>
Line 5,767 ⟶ 6,669:
</ul>
</body>
</html></
=={{header|zkl}}==
With 64 bit ints:
<
acc:=fcn(n,k,acc,maxD){ // k is 2,3,5,7,9,... not optimum
if(n==1 or k>maxD) acc.close();
Line 5,783 ⟶ 6,685:
if(n!=m) acc.append(n/m); // opps, missed last factor
else acc;
}</
<
9007199254740991, 576460752303423487)){
println(n,": ",primeFactors(n).concat(", "))
}</
{{out}}
<pre>
Line 5,799 ⟶ 6,701:
</pre>
Unfortunately, big ints (GMP) don't have (quite) the same interface as ints (since there is no big float, BI.toFloat() truncates to a double so BI.toFloat().sqrt() is wrong). So mostly duplicate code is needed:
<
acc:=fcn(n,k,acc,maxD){ // k is 2,3,5,7,9,... not optimum
if(n==1 or k>maxD) acc.close();
Line 5,811 ⟶ 6,713:
if(n!=m) acc.append(n/m); // opps, missed last factor
else acc;
}</
<
foreach n in (T(BN("12"),
BN("340282366920938463463374607431768211455"))){
println(n,": ",factorsBI(n).concat(", "))
}</
{{out}}
<pre>
|