Prime decomposition: Difference between revisions
→{{header|Picat}}
(Add BQN) |
|||
Line 3,548:
"1.1s"
</pre>
=={{header|Picat}}==
<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.</lang>
{{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}}==
| |||