Prime decomposition: Difference between revisions
Dialects of BASIC moved to the BASIC section.
(→Python: Using Croft Spiral sieve: make croft() another ~1.5% faster by duplicating only once per entry; remove unused dict inits) |
(Dialects of BASIC moved to the BASIC section.) |
||
Line 758:
99: 3 3 11
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">decompose: function [num][
facts: to [:string] factors.prime num
Line 898 ⟶ 882:
{{out}}
<pre>8388607 = 47 * 178481</pre>
=={{header|AWK}}==
Line 929 ⟶ 912:
8796093022207
431 9719 2099863</pre>
=={{header|BASIC}}==
==={{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|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|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|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}}==
Line 1,686 ⟶ 2,047:
(recur (quot n k) k (cons k acc))
(recur n (inc k) acc)))))</syntaxhighlight>
=={{header|Common Lisp}}==
Line 2,038 ⟶ 2,378:
=={{header|ERRE}}==
{{trans|Commodore BASIC}}
<syntaxhighlight lang="erre">
PROGRAM DECOMPOSE
Line 2,089 ⟶ 2,430:
END PROGRAM
</syntaxhighlight>
=={{header|Ezhil}}==
Line 2,326 ⟶ 2,666:
end program Primes</syntaxhighlight>
=={{header|Frink}}==
Line 3,993 ⟶ 4,258:
= factor (k+2) n otherwise;
end;</syntaxhighlight>
=={{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]].
Line 4,955 ⟶ 5,176:
}
</syntaxhighlight>
=={{header|Scala}}==
Line 5,575 ⟶ 5,734:
2**59-1 = 576460752303423487 = 179951*3203431780337 => 316009 microseconds per iteration</pre>
=={{header|TXR}}==
{{trans|Common Lisp}}
<syntaxhighlight lang="txr">@(next :args)
@(do
Line 5,749 ⟶ 5,801:
<syntaxhighlight lang="v">|1221 prime-decomposition puts</syntaxhighlight>
=[3 11 37]
=={{header|Wren}}==
| |||