Prime decomposition: Difference between revisions
→{{header|PowerShell}}
(→{{header|C}}: prime decomposition of a number N (64-bit) in C language) |
Lijice4777 (talk | contribs) |
||
| (42 intermediate revisions by 16 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]].
<
# Prime sieve
primes ← ↕0
Line 987 ⟶ 1,668:
Try 2
r ∾ 1⊸<⊸⥊n
}</
{{out}}
<
┌─
╵ 1232123 ⟨ 29 42487 ⟩
Line 995 ⟶ 1,676:
1232125 ⟨ 5 5 5 9857 ⟩
1232126 ⟨ 2 7 17 31 167 ⟩
┘</
=={{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}}==
Line 1,009 ⟶ 1,710:
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,179 ⟶ 1,880:
return 0;
}</
===Using GNU Compiler Collection gcc extensions===
Line 1,191 ⟶ 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,297 ⟶ 1,998:
CONTINUE;
}
}</
{{out}}
<pre>
Line 1,320 ⟶ 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,392 ⟶ 2,093:
return 0;
}</
===Version 2===
<syntaxhighlight lang="c">
typedef unsigned long long int ulong; // define a type that represent the limit (64-bit)
Line 1,413 ⟶ 2,114:
ulong square_root(const ulong N) {
ulong res = 0, rem = N, c, d;
for (c = 1 <<
d = res + c;
res >>= 1;
Line 1,476 ⟶ 2,177:
}
</syntaxhighlight>
=={{header|C sharp|C#}}==
<
using System.Collections.Generic;
Line 1,522 ⟶ 2,223:
}
}
}</
===Simple trial division===
Line 1,528 ⟶ 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,544 ⟶ 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,633 ⟶ 2,334:
std::cout << "\n";
}
}</
=== Simple trial division ===
<
#include <iostream>
Line 1,670 ⟶ 2,371:
}
return 0;
}</
=={{header|Clojure}}==
<
(defn factors
"Return a list of factors of N."
Line 1,683 ⟶ 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,714 ⟶ 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,726 ⟶ 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,755 ⟶ 2,435:
decompose(16860167264933UL.BigInt * 179951).writeln;
decompose(2.BigInt ^^ 100_000).group.writeln;
}</
{{out}}
<pre>[2]
Line 1,772 ⟶ 2,452:
{{libheader| System.SysUtils}}
{{Trans|C#}}
<syntaxhighlight lang="delphi">
program Prime_decomposition;
Line 1,826 ⟶ 2,506:
write(v, ' ');
readln;
end.</
=={{header|E}}==
Line 1,832 ⟶ 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,860 ⟶ 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,873 ⟶ 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,915 ⟶ 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,927 ⟶ 2,626:
=={{header|Ela}}==
{{trans|F#}}
<
decompose_prime n = loop n 2I
Line 1,935 ⟶ 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,954 ⟶ 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,977 ⟶ 2,750:
=={{header|Erlang}}==
<
factors(N) ->
Line 1,987 ⟶ 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 2,040 ⟶ 2,814:
PRINT
END PROGRAM
</syntaxhighlight>
=={{header|Ezhil}}==
<syntaxhighlight lang="ezhil">
## இந்த நிரல் தரப்பட்ட எண்ணின் பகாஎண் கூறுகளைக் கண்டறியும்
Line 2,188 ⟶ 2,961:
பதிப்பி "நீங்கள் தந்த எண்ணின் பகா எண் கூறுகள் இவை: ", பகாஎண்கூறுகள்
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
<
let rec loop c p =
if c < (p * p) then [c]
Line 2,199 ⟶ 2,972:
loop n 2I
printfn "%A" (decompose_prime 600851475143I)</
{{out}}
<pre>[71; 839; 1471; 6857]</pre>
Line 2,205 ⟶ 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,224 ⟶ 2,997:
then
repeat
drop . ;</
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
implicit none
Line 2,258 ⟶ 3,031:
end subroutine find_factors
end module PrimeDecompose</
<
use PrimeDecompose
implicit none
Line 2,276 ⟶ 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,368 ⟶ 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,413 ⟶ 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,426 ⟶ 3,124:
so it does not require an "isPrime-like function",
assumed or otherwise.
<
if (target == 1) return [1L]
Line 2,454 ⟶ 3,152:
}
primeFactors
}</
{{out|Test #1}}
<
{{out|Output #1}}
Line 2,496 ⟶ 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,522 ⟶ 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,539 ⟶ 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,568 ⟶ 3,266:
=={{header|Icon}} and {{header|Unicon}}==
<
factors := primedecomp(2^43-1) # a big int
end
Line 2,585 ⟶ 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,593 ⟶ 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,612 ⟶ 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,625 ⟶ 3,323:
}
return ans;
}</
Alternate version, optimised to be faster.
<
public List<BigInteger> primeDecomp(BigInteger a) {
Line 2,659 ⟶ 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,706 ⟶ 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,721 ⟶ 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,763 ⟶ 3,461:
divisor = divisor.add(TWO);
}
}</
Without any library.
<
if (n <= 3)
return [n];
Line 2,805 ⟶ 3,503:
ans.push(n);
return ans;
}</
TDD using Jasmine
PrimeFactors.js
<
if (!n || n < 2)
return [];
Line 2,824 ⟶ 3,522:
return f;
};
</syntaxhighlight>
SpecPrimeFactors.js (with tag for Chutzpah)
<
describe("Prime Factors", function() {
Line 2,875 ⟶ 3,573:
});
});
</syntaxhighlight>
=={{header|jq}}==
Line 2,895 ⟶ 3,593:
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]
Line 2,908 ⟶ 3,606:
end
end )
| if .[2] then .[0] else empty end ;</
'''Examples''':
<syntaxhighlight lang="jq">
24 | factors
#=> 2 2 2 3
Line 2,919 ⟶ 3,617:
# 2**29-1 is 536870911
[ 536870911 | factors ]
#=> [233,1103,2089]</
=={{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,966 ⟶ 3,664:
println("2^${"%2d".format(prime)} - 1 = ${bigPow2.toString().padEnd(30)} => ${getPrimeFactors(bigPow2)}")
}
}</
{{out}}
Line 2,998 ⟶ 3,696:
=={{header|Lambdatalk}}==
<
{def prime_fact.smallest
{def prime_fact.smallest.r
Line 3,030 ⟶ 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 3,045 ⟶ 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 3,070 ⟶ 3,768:
f.add(n)
return f
end</
<
-- [2.0000, 2.0000, 3.0000]
Line 3,081 ⟶ 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 3,094 ⟶ 3,792:
is located at [[Primality by trial division#Lua]]
<
local f = {}
Line 3,115 ⟶ 3,813:
return f
end</
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module Prime_decomposition {
Inventory Known1=2@, 3@
Line 3,169 ⟶ 3,867:
}
Prime_decomposition
</syntaxhighlight>
=={{header|Maple}}==
Line 3,177 ⟶ 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,222 ⟶ 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,241 ⟶ 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,265 ⟶ 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,282 ⟶ 4,054:
=={{header|Nim}}==
Based on python floating point solution, but using integers rather than floats.
<
proc getStep(n: int64): int64 {.inline.} =
Line 3,319 ⟶ 4,091:
let start = cpuTime()
stdout.write primeFac(p).join(", ")
echo &" => {(1000 * (cpuTime() - start)).toInt} ms"</
{{out}}
Line 3,342 ⟶ 4,114:
=={{header|OCaml}}==
<
let prime_decomposition x =
Line 3,353 ⟶ 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,362 ⟶ 4,134:
Oforth handles aribitrary precision integers.
<
| k p |
ListBuffer new
Line 3,375 ⟶ 4,147:
]
n 1 > ifTrue: [ n over add ]
dup freeze ;</
{{out}}
Line 3,391 ⟶ 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,399 ⟶ 4,171:
);
vecsort(v)
};</
=={{header|Pascal}}==
<
type
Line 3,439 ⟶ 4,211:
for j := low(factors) to high(factors) do
writeln (factors[j]);
end.</
{{out}}
<pre>% ./PrimeDecomposition
Line 3,458 ⟶ 4,230:
'''Optimization:'''
<
type
Line 3,503 ⟶ 4,275:
writeln (factors[j]);
readln;
end.</
=={{header|Perl}}==
Line 3,510 ⟶ 4,282:
===Trivial trial division (very slow)===
<
my ($n, $d, @out) = (shift, 1);
while ($n > 1 && $d++) {
Line 3,518 ⟶ 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,535 ⟶ 4,307:
push @out, $n if $n > 1;
@out;
}</
===Modules===
Line 3,541 ⟶ 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,547 ⟶ 4,319:
my $p = 2 ** $_ - 1;
print "2**$_-1: ", join(" ", factor($p)), "\n";
} 100, 150;</
{{out}}
<pre>
Line 3,563 ⟶ 4,335:
{{libheader|Math::Pari}}
<
# Convert Math::Pari's format into simple vector
Line 3,575 ⟶ 4,347:
my $p = 2 ** $_ - 1;
print "2^$_-1: ", join(" ", factor($p)), "\n";
}</
With the same output.
Line 3,581 ⟶ 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,596 ⟶ 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,633 ⟶ 4,403:
600851475143 = 71*839*1471*6857
100000000000000000037 = 31*821*59004541*66590107
"
</pre>
=={{header|Picat}}==
<
% Checking 2**prime-1
foreach(P in primes(60))
Line 3,675 ⟶ 4,445:
Divisors := Divisors ++ [Div],
M := M div Div
end.</
{{out}}
Line 3,702 ⟶ 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,711 ⟶ 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,754 ⟶ 4,592:
end test;
</syntaxhighlight>
{{out|Results from various runs}}
<pre>
Line 3,767 ⟶ 4,605:
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
function eratosthenes ($n) {
if($n -gt 1){
Line 3,798 ⟶ 4,636:
$prime
}
"$(prime-decomposition
"$(prime-decomposition
</syntaxhighlight>
<b>Output:</b>
<pre>
Line 3,806 ⟶ 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,844 ⟶ 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,857 ⟶ 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,863 ⟶ 4,721:
Optimized to stop on square root, and count by +2 on odds, above 2.
<
factors2( N, FS).
Line 3,878 ⟶ 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,918 ⟶ 4,776:
reverse_factors(A*B, C*A) :- reverse_factors(B, C), !.
reverse_factors(A, A).
</syntaxhighlight>
{{Out}}
<pre>
Line 3,941 ⟶ 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 4,017 ⟶ 4,823:
self[n] = r
return r
is_prime_cached = IsPrimeCached()
def croft():
"""Yield prime integers using the Croft Spiral sieve.
Line 4,035 ⟶ 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 4,070 ⟶ 4,872:
if __name__ == '__main__':
# Example: calculate factors of Mersenne numbers to M59 #
import time
for m in primes():
p = 2 ** m - 1
Line 4,080 ⟶ 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 4,123 ⟶ 4,925:
Here a shorter and marginally faster algorithm:
<
try:
long
Line 4,144 ⟶ 4,946:
tocalc = 2**59-1
print("%s = %s" % (tocalc, fac(tocalc)))
print("Needed %ss" % (time.time() - start))</
{{out}}
Line 4,152 ⟶ 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,161 ⟶ 4,969:
drop
dup 1 = if conclude ]
drop ] is primefactors ( n --> [ )</syntaxhighlight>
{{out}}
Line 4,170 ⟶ 4,976:
=={{header|R}}==
<
x <- NULL
firstprime<- 2; secondprime <- 3; everyprime <- num
Line 4,184 ⟶ 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,225 ⟶ 5,031:
}
}
</syntaxhighlight>
=== Alternate solution ===
<
a <- NULL
if (n > 1) {
Line 4,245 ⟶ 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,264 ⟶ 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,271 ⟶ 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,307 ⟶ 5,113:
"factors of $n: ",
prime-factors($n).join(' × '), " \t in ", (now - $start).fmt("%0.3f"), " sec."
}</
{{out}}
Line 4,323 ⟶ 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,338 ⟶ 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,362 ⟶ 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,412 ⟶ 5,258:
<pre style="font-size:75%;height:160ex">
1 (0) prime factors: {unity}
2 (1) prime factors: [prime] 2
Line 4,538 ⟶ 5,385:
<pre style="font-size:75%>
3 (1) prime factors: [prime] 3
7 (1) prime factors: [prime] 7
Line 4,550 ⟶ 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,614 ⟶ 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,653 ⟶ 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,725 ⟶ 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,747 ⟶ 5,662:
factors = prime_factors(2**i-1)
puts "2**#{i}-1 = #{2**i-1} = #{factors.join(' * ')}"
end</
{{out}}
<pre>...
Line 4,756 ⟶ 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,787 ⟶ 5,702:
factors = prime_factors_faster(2**i-1)
puts "2**#{i}-1 = #{2**i-1} = #{factors.join(' * ')}"
end</
{{out}}
<pre>...
Line 4,797 ⟶ 5,712:
This benchmark compares the different implementations.
<
require 'mathn'
Benchmark.bm(24) do |x|
Line 4,806 ⟶ 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,828 ⟶ 5,743:
The implementation:
<
use num_traits::{One, Zero};
use std::fmt::{Display, Formatter};
Line 4,920 ⟶ 5,835:
}
}
</syntaxhighlight>
=={{header|Scala}}==
{{libheader|Scala}}
<
import collection.parallel.mutable.ParSeq
Line 5,029 ⟶ 5,881:
}
}
}</
{{out}}
<pre>
Line 5,052 ⟶ 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 5,084 ⟶ 5,936:
def hasNext = currentN != one && currentN > zero
}</
The method isProbablePrime(n) has a chance of 1 - 1/(2^n) of correctly
Line 5,090 ⟶ 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 5,114 ⟶ 5,966:
def hasNext = currentN != one && currentN > zero
}</
{{out}}
Both versions can be rather slow, as they accept arbitrarily big numbers,
Line 5,143 ⟶ 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 5,158 ⟶ 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 5,180 ⟶ 6,032:
result &:= [](number);
end if;
end func;</
Original source: [http://seed7.sourceforge.net/algorith/math.htm#factorise]
Line 5,187 ⟶ 6,039:
'''Recursive Using isPrime'''
<
primeFactorization(num) := primeFactorizationHelp(num, []);
Line 5,197 ⟶ 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,203 ⟶ 6,055:
'''Recursive Trial Division'''
<
primeFactorizationHelp(num, divisor, factors(1)) :=
Line 5,210 ⟶ 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,235 ⟶ 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,324 ⟶ 6,176:
END;
</syntaxhighlight>
{{out}}
<pre>
Line 5,337 ⟶ 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,351 ⟶ 6,203:
[div: next.
next: next + 2] "Just look at the next odd integer."
].</
=={{header|Smalltalk}}==
<
primesDo: aBlock [
| div next rest |
Line 5,368 ⟶ 6,220:
]
]
123456 primesDo: [ :each | each printNl ]</
=={{header|SPAD}}==
{{works with|FriCAS, OpenAxiom, Axiom}}
<syntaxhighlight lang="spad">
(1) -> factor 102400
Line 5,384 ⟶ 6,236:
Type: Factored(Integer)
</syntaxhighlight>
Domain:[http://fricas.github.io/api/Factored.html?highlight=factor Factored(R)]
Line 5,390 ⟶ 6,242:
=={{header|Standard ML}}==
Trial division
<syntaxhighlight lang="sml">
val factor = fn n :IntInf.int =>
let
Line 5,412 ⟶ 6,264:
end;
</syntaxhighlight>
<pre>
- Array.fromList(factor 122489234920000001278234798233);;
Line 5,422 ⟶ 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,447 ⟶ 6,299:
return(a)
}
}</
=={{header|Swift}}==
Line 5,454 ⟶ 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,478 ⟶ 6,330:
print("2^\(prime) - 1 = \(m) => \(decom)")
}</
{{out}}
Line 5,500 ⟶ 6,352:
=={{header|Tcl}}==
<
# list the prime factors of x in ascending order
set result [list]
Line 5,516 ⟶ 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,542 ⟶ 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,666 ⟶ 6,412:
@(output)
@num -> {@(rep)@factors, @(last)@factors@(end)}
@(end)</
{{out}}
<pre>$ txr factor.txr 1139423842450982345
Line 5,689 ⟶ 6,435:
=={{header|V}}==
like in scheme (using variables)
<
[inner [c p] let
[c c * p >]
Line 5,698 ⟶ 6,444:
ifte]
ifte].
2 swap inner].</
(mostly) the same thing using stack (with out variables)
<
[inner
[dup * <]
Line 5,710 ⟶ 6,456:
ifte]
ifte].
2 inner].</
Using it
<syntaxhighlight lang
=[3 11 37]
=={{header|Wren}}==
Line 5,774 ⟶ 6,466:
{{libheader|Wren-fmt}}
The examples are borrowed from the Go solution.
<
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, BigInt.primeFactors(val))
}</
{{out}}
Line 5,791 ⟶ 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,865 ⟶ 6,616:
</xsl:template>
</xsl:stylesheet></
is applied against the document
<
<number><value>1</value></number>
<number><value>2</value></number>
Line 5,874 ⟶ 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,918 ⟶ 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,934 ⟶ 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,950 ⟶ 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,962 ⟶ 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>
| |||