Factors of a Mersenne number: Difference between revisions
Added Easylang
(Add Swift) |
(Added Easylang) |
||
(46 intermediate revisions by 17 users not shown) | |||
Line 57:
;See also:
* [https://www.youtube.com/watch?v=SNwvJ7psoow Computers in 1948: 2
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F is_prime(a)
I a == 2 {R 1B}
I a < 2 | a % 2 == 0 {R 0B}
L(i) (3 .. Int(sqrt(a))).step(2)
I a % i == 0
R 0B
R 1B
F m_factor(p)
V max_k = 16384 I/ p
L(k) 0 .< max_k
V q = 2 * p * k + 1
I !is_prime(q)
L.continue
E I q % 8 != 1 & q % 8 != 7
L.continue
E I pow(2, p, q) == 1
R q
R 0
V exponent = Int(input(‘Enter exponent of Mersenne number: ’))
I !is_prime(exponent)
print(‘Exponent is not prime: #.’.format(exponent))
E
V factor = m_factor(exponent)
I factor == 0
print(‘No factor found for M#.’.format(exponent))
E
print(‘M#. has a factor: #.’.format(exponent, factor))</syntaxhighlight>
{{out}}
<pre>
Enter exponent of Mersenne number: 929
M929 has a factor: 13007
</pre>
=={{header|8086 Assembly}}==
<syntaxhighlight lang="asm">P: equ 929 ; P for 2^P-1
cpu 8086
bits 16
org 100h
section .text
mov ax,P ; Is P prime?
call prime
mov dx,notprm
jc msg ; If not, say so and stop.
xor bp,bp ; Let BP hold k
test_k: inc bp ; k += 1
mov ax,P ; Calculate 2kP + 1
mul bp ; AX = kP
shl ax,1 ; AX = 2kP
inc ax ; AX = 2kP + 1
mov dx,ovfl ; If AX overflows (16 bits), say so and stop
jc msg
mov bx,ax ; What is 2^P mod (2kP+1)?
mov cx,P
call modpow
dec ax ; If it is 1, we're done
jnz test_k ; If not, increment K and try again
mov dx,factor ; If so, we found a factor
call msg
prbx: mov ax,10 ; The factor is still in BX
xchg bx,ax ; Put factor in AX and divisor (10) in BX
mov di,number ; Generate ASCII representation of number
digit: xor dx,dx
div bx ; Divide current number by 10,
add dl,'0' ; add '0' to remainder,
dec di ; move pointer back,
mov [di],dl ; store digit,
test ax,ax ; and if there are more digits,
jnz digit ; find the next digit.
mov dx,di ; Finally, print the number.
jmp msg
;;; Calculate 2^CX mod BX
;;; Output: AX
;;; Destroyed: CX, DX
modpow: shl cx,1 ; Shift CX left until top bit in high bit
jnc modpow ; Keep shifting while carry zero
rcr cx,1 ; Put the top bit back into CX
mov ax,1 ; Start with square = 1
.step: mul ax ; Square (result is 32-bit, goes in DX:AX)
shl cx,1 ; Grab a bit from CX
jnc .nodbl ; If zero, don't multiply by two
shl ax,1 ; Shift DX:AX left (mul by two)
rcl dx,1
.nodbl: div bx ; Divide DX:AX by BX (putting modulus in DX)
mov ax,dx ; Continue with modulus
jcxz .done ; When CX reaches 0, we're done
jmp .step ; Otherwise, do the next step
.done: ret
;;; Is AX prime?
;;; Output: carry clear if prime, set if not prime.
;;; Destroyed: AX, BX, CX, DX, SI, DI, BP
prime: mov cx,[prcnt] ; See if AX is already in the list of primes
mov di,primes
repne scasw ; If so, return
je modpow.done ; Reuse the RET just above here (carry clear)
mov bp,ax ; Move AX out of the way
mov bx,[di-2] ; Start generating new primes
.sieve: inc bx ; BX = last prime + 2
inc bx
cmp bp,bx ; If BX higher than number to test,
jb modpow.done ; stop, number is not prime. (carry set)
mov cx,[prcnt] ; CX = amount of current primes
mov si,primes ; SI = start of primes
.try: mov ax,bx ; BX divisible by current prime?
xor dx,dx
div word [si]
test dx,dx ; If so, BX is not prime.
jz .sieve
inc si
inc si
loop .try ; Otherwise, try next prime.
mov ax,bx ; If we get here, BX _is_ prime
stosw ; So add it to the list
inc word [prcnt] ; We have one more prime
cmp ax,bp ; Is it the prime we are looking for?
jne .sieve ; If not, try next prime
ret
;;; Print message in DX
msg: mov ah,9
int 21h
ret
section .data
db "*****" ; Placeholder for number
number: db "$"
notprm: db "P is not prime.$"
ovfl: db "Range of factor exceeded (max 16 bits)."
factor: db "Found factor: $"
prcnt: dw 2 ; Amount of primes currently in list
primes: dw 2, 3 ; List of primes to be extended</syntaxhighlight>
{{out}}
<pre>Found factor: 13007</pre>
=={{header|360 Assembly}}==
Line 64 ⟶ 204:
Use of bitwise operations
(TM (Test under Mask), SLA (Shift Left Arithmetic),SRA (Shift Right Arithmetic)).
<syntaxhighlight lang="text">* Factors of a Mersenne number 11/09/2015
MERSENNE CSECT
USING MERSENNE,R15
Line 153 ⟶ 293:
PG DS CL24 buffer
YREGS
END MERSENNE</
{{out}}
<pre>
Line 161 ⟶ 301:
=={{header|Ada}}==
mersenne.adb:
<
-- reuse Is_Prime from [[Primality by Trial Division]]
with Is_Prime;
Line 228 ⟶ 368:
Ada.Text_IO.Put_Line ("is not a Mersenne number");
end;
end Mersenne;</
{{out}}
Line 240 ⟶ 380:
<!-- {{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}
Compiles, but I couldn't maxint not in library, works with manually entered maxint, bits width. Leaving some issue with newline -->
<
PR READ "prelude/is_prime.a68" PR;
Line 290 ⟶ 430:
FI
END</
Example:
<pre>
Line 296 ⟶ 436:
M +929 has a factor: +13007
</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">mersenneFactors: function [q][
if not? prime? q -> print "number not prime!"
r: new q
while -> r > 0
-> shl 'r 1
d: new 1 + 2 * q
while [true][
i: new 1
p: new r
while [p <> 0][
i: new (i * i) % d
if p < 0 -> 'i * 2
if i > d -> 'i - d
shl 'p 1
]
if? i <> 1 -> 'd + 2 * q
else -> break
]
print ["2 ^" q "- 1 = 0 ( mod" d ")"]
]
mersenneFactors 929</syntaxhighlight>
{{out}}
<pre>2 ^ 929 - 1 = 0 ( mod 13007 )</pre>
=={{header|AutoHotkey}}==
ahk [http://www.autohotkey.com/forum/viewtopic.php?t=44657&postdays=0&postorder=asc&start=144 discussion]
<
MsgBox % MFact(2) ; 0
MsgBox % MFact(3) ; 0
Line 354 ⟶ 523:
y := i&1 ? mod(y*z,m) : y, z := mod(z*z,m), i >>= 1
Return y
}</
=={{header|BBC BASIC}}==
<
PRINT "A factor of M937 is "; FNmersenne_factor(937)
END
Line 394 ⟶ 563:
ENDWHILE
= Y%
</syntaxhighlight>
{{out}}
<pre>A factor of M929 is 13007
Line 400 ⟶ 569:
=={{header|Bracmat}}==
<
= square P divisor highbit log 2pow
. !arg:(?P.?divisor)
Line 461 ⟶ 630:
| out$"no divisors found"
)
);</
{{out}}
<pre>found some divisors of 2^!P-1 : 13007 and 348890248924938259750454781163390930305120269538278042934009621348894657205785
Line 469 ⟶ 638:
=={{header|C}}==
<
if (n%2==0) return n==2;
if (n%3==0) return n==3;
Line 492 ⟶ 661:
else break;
} while(1);
printf("2^%d - 1 = 0 (mod %d)\n", q, d);}</
=={{header|C sharp|C#}}==
<
namespace prog
Line 540 ⟶ 709:
}
}
}</
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <iostream>
#include <cstdint>
typedef uint64_t integer;
integer bit_count(integer n) {
integer count = 0;
for (; n > 0; count++)
n >>= 1;
return count;
}
integer mod_pow(integer p, integer n) {
integer square = 1;
for (integer bits = bit_count(p); bits > 0; square %= n) {
square *= square;
if (p & (1 << --bits))
square <<= 1;
}
return square;
}
bool is_prime(integer n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
for (integer p = 3; p * p <= n; p += 2)
if (n % p == 0)
return false;
return true;
}
integer find_mersenne_factor(integer p) {
for (integer k = 0, q = 1;;) {
q = 2 * ++k * p + 1;
if ((q % 8 == 1 || q % 8 == 7) && mod_pow(p, q) == 1 && is_prime(q))
return q;
}
return 0;
}
int main() {
std::cout << find_mersenne_factor(929) << std::endl;
return 0;
}</syntaxhighlight>
{{out}}
<pre>
13007
</pre>
=={{header|Clojure}}==
{{trans|Python}}
<
(:gen-class))
Line 603 ⟶ 825:
:let [s (-main p)]]
(println s))
</syntaxhighlight>
{{Output}}
<pre>
Line 631 ⟶ 853:
{{trans|Ruby}}
<
limit = Math.sqrt(Math.pow(2,p) - 1)
k = 1
Line 658 ⟶ 880:
checkMersenne(prime) for prime in ["2","3","4","5","7","11","13","17","19","23","29","31","37","41","43","47","53","929"]
</syntaxhighlight>
<pre>M2 = 2^2-1 is prime
Line 682 ⟶ 904:
=={{header|Common Lisp}}==
{{trans|Maxima}}
<
(loop for k from 1
for n = (1+ (* 2 k p))
Line 688 ⟶ 910:
finally (return n)))
(print (mersenne-fac 929))</
{{out}}
Line 697 ⟶ 919:
We can use a primality test from the [[Primality by Trial Division#Common_Lisp|Primality by Trial Division]] task.
<
"Is N prime?"
(and (> n 1)
(or (= n 2) (oddp n))
(loop for i from 3 to (isqrt n) by 2
never (zerop (rem n i)))))</
Specific to this task, we define modulo-power and mersenne-prime-p.
<
(loop with square = 1
for bit across (format nil "~b" power)
Line 724 ⟶ 946:
(primep q)
(= 1 (modulo-power 2 power q)))
(return (values nil q)))))</
We can run the same tests from the [[#Ruby|Ruby]] entry.
Line 751 ⟶ 973:
M53 = 2**53-1 is composite with factor 6361.
M929 = 2**929-1 is composite with factor 13007.</pre>
=={{header|Crystal}}==
{{trans|Ruby}}
<syntaxhighlight lang="ruby">require "big"
def prime?(n) # P3 Prime Generator primality test
return n | 1 == 3 if n < 5 # n: 0,1,4|false, 2,3|true
return false if n.gcd(6) != 1 # for n a P3 prime candidate (pc)
pc1, pc2 = -1, 1 # use P3's prime candidates sequence
until (pc1 += 6) > Math.sqrt(n).to_i # pcs are only 1/3 of all integers
return false if n % pc1 == 0 || n % (pc2 += 6) == 0 # if n is composite
end
true
end
# Compute b**e mod m
def powmod(b, e, m)
r, b = 1.to_big_i, b.to_big_i
while e > 0
r = (r * b) % m if e.odd?
b = (b * b) % m
e >>= 1
end
r
end
def mersenne_factor(p)
mers_num = 2.to_big_i ** p - 1
kp2 = p2 = 2.to_big_i * p
while (kp2 - 1) ** 2 < mers_num
q = kp2 + 1 # return q if it's a factor
return q if [1, 7].includes?(q % 8) && prime?(q) && (powmod(2, p, q) == 1)
kp2 += p2
end
true # could also set to `0` value to check for
end
def check_mersenne(p)
print "M#{p} = 2**#{p}-1 is "
f = mersenne_factor(p)
(puts "prime"; return) if f.is_a?(Bool) # or f == 0
puts "composite with factor #{f}"
end
(2..53).each { |p| check_mersenne(p) if prime?(p) }
check_mersenne 929</syntaxhighlight>
{{out}}
<pre>M2 = 2**2-1 is prime
M3 = 2**3-1 is prime
M5 = 2**5-1 is prime
M7 = 2**7-1 is prime
M11 = 2**11-1 is composite with factor 23
M13 = 2**13-1 is prime
M17 = 2**17-1 is prime
M19 = 2**19-1 is prime
M23 = 2**23-1 is composite with factor 47
M29 = 2**29-1 is composite with factor 233
M31 = 2**31-1 is prime
M37 = 2**37-1 is composite with factor 223
M41 = 2**41-1 is composite with factor 13367
M43 = 2**43-1 is composite with factor 431
M47 = 2**47-1 is composite with factor 2351
M53 = 2**53-1 is composite with factor 6361
M929 = 2**929-1 is composite with factor 13007</pre>
=={{header|D}}==
<
ulong mersenneFactor(in ulong p) pure nothrow @nogc {
Line 789 ⟶ 1,076:
void main() {
writefln("Factor of M929: %d", 929.mersenneFactor);
}</
{{out}}
<pre>Factor of M929: 13007</pre>
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Factors_of_a_Mersenne_number#Pascal Pascal].
=={{header|EasyLang}}==
{{trans|C++}}
<syntaxhighlight>
fastfunc isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
func bit_count n .
while n > 0
n = bitshift n -1
cnt += 1
.
return cnt
.
func mod_pow p n .
square = 1
bits = bit_count p
while bits > 0
square *= square
bits -= 1
if bitand p bitshift 1 bits > 0
square = bitshift square 1
.
square = square mod n
.
return square
.
func mersenne_factor p .
while 1 = 1
k += 1
q = 2 * k * p + 1
if (q mod 8 = 1 or q mod 8 = 7) and mod_pow p q = 1 and isprim q = 1
return q
.
.
.
print mersenne_factor 929
</syntaxhighlight>
{{out}}
<pre>
13007
</pre>
=={{header|EchoLisp}}==
<
;; M = 2^P - 1 , P prime
;; look for a prime divisor q such as : q < √ M, q = 1 or 7 modulo 8, q = 1 + 2kP
Line 818 ⟶ 1,157:
→ #t
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Ruby}}
<
def mersenne_factor(p) do
limit = :math.sqrt(:math.pow(2, p) - 1)
Line 857 ⟶ 1,196:
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,929]
|> Enum.each(fn p -> Mersenne.check_mersenne(p) end)</
{{out}}
Line 884 ⟶ 1,223:
The modpow function is not my original. This is a translation of python, more or less.
<
-module(mersene2).
-export([prime/1,modpow/3,mf/1]).
Line 927 ⟶ 1,266:
false -> divisors(N, C-1)
end.
</syntaxhighlight>
{{out}}
<pre>
Line 942 ⟶ 1,281:
=={{header|Factor}}==
<
math math.bits math.functions math.primes sequences ;
IN: rosetta-code.mersenne-factors
Line 973 ⟶ 1,312:
[ [I No factor found for M${}.I] ] if* nl ;
929 test-mersenne</
{{out}}
<pre>
Line 980 ⟶ 1,319:
=={{header|Forth}}==
<
3
begin 2dup dup * >=
Line 1,012 ⟶ 1,351:
929 factor-mersenne . \ 13007
4423 factor-mersenne . \ 0</
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
IMPLICIT NONE
INTEGER :: exponent, factor
Line 1,067 ⟶ 1,406:
Mfactor = 0
END FUNCTION
END PROGRAM EXAMPLE</
{{out}}
M929 has a factor: 13007
Line 1,073 ⟶ 1,412:
=={{header|FreeBASIC}}==
{{trans|C}}
<
Function isPrime(n As Integer) As Boolean
Line 1,117 ⟶ 1,456:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 1,137 ⟶ 1,476:
2^97 - 1 = 0 (mod 11447)
2^929 - 1 = 0 (mod 13007)
</pre>
=={{header|Frink}}==
Frink has built-in routines for iterating through prime numbers and modular exponentiation. The following program will find all of the factors of the number given enough runtime.
<syntaxhighlight lang="frink">for p = primes[]
if modPow[2, 929, p] - 1 == 0
println[p]</syntaxhighlight>
{{out}}
<pre>
13007
</pre>
=={{header|GAP}}==
<
local k, m, d;
if IsPrime(n) then
Line 1,171 ⟶ 1,520:
FactorsInt(2^101-1);
# [ 7432339208719, 341117531003194129 ]</
=={{header|Go}}==
<
import (
Line 1,254 ⟶ 1,603:
}
return int32(pow)
}</
{{out}}
<pre>
Line 1,266 ⟶ 1,615:
Using David Amos module Primes [https://web.archive.org/web/20121130222921/http://www.polyomino.f2s.com/david/haskell/codeindex.html] for prime number testing:
<
import HFM.Primes (isPrime)
import Control.Monad
Line 1,278 ⟶ 1,627:
map (succ.(2*m*)). enumFromTo 1 $ m `div` 2
bs = int2bin m
pm n b = 2^b*n*n</
<
[13007]</
=={{header|Icon}} and {{header|Unicon}}==
Line 1,287 ⟶ 1,636:
The following works in both languages:
<
p := integer(A[1]) | 929
write("M",p," has a factor ",mfactor(p))
Line 1,318 ⟶ 1,667:
}
return
end</
Sample runs:
Line 1,331 ⟶ 1,680:
=={{header|J}}==
<
qs=. (#~8&(1=|+.7=|))(#~1&p:)1+(*(1x+i.@<:@<.)&.-:)y
qs#~1=qs&|@(2&^@[**:@])/ 1,~ |.#: y
)</
{{out|Examples}}
<
13007</
<syntaxhighlight lang
Empty output --> No factors found.
=={{header|Java}}==
<
import java.math.BigInteger;
Line 1,412 ⟶ 1,761:
}
</syntaxhighlight>
{{out}}
Line 1,439 ⟶ 1,788:
=={{header|JavaScript}}==
<
var limit, k, q
limit = Math.sqrt(Math.pow(2,p) - 1)
Line 1,479 ⟶ 1,828:
f = mersenne_factor(p)
console.log(f == null ? "prime" : "composite with factor "+f)
}</
<pre>
Line 1,491 ⟶ 1,840:
=={{header|Julia}}==
<
using Primes
Line 1,511 ⟶ 1,860:
if mf != -1 println("M$i = ", mf, " × ", (big(2) ^ i - 1) ÷ mf)
else println("M$i is prime") end
end</
{{out}}
Line 1,529 ⟶ 1,878:
=={{header|Kotlin}}==
{{trans|C}}
<
fun isPrime(n: Int): Boolean {
Line 1,575 ⟶ 1,924:
}
}
}</
{{out}}
Line 1,598 ⟶ 1,947:
=={{header|Lingo}}==
<
bits = getBits(e)
sq = 1
Line 1,620 ⟶ 1,969:
end repeat
return bits
end</
<
if modPow(2, 929, i)=1 then
put "M929 has a factor: " & i
exit repeat
end if
end repeat</
{{out}}
Line 1,634 ⟶ 1,983:
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Believe it or not, this type of test runs faster in Mathematica than the squaring version described above.
<syntaxhighlight lang="mathematica">For[i = 2, i < Prime[1000000], i = NextPrime[i],
If[Mod[2^44497, i] == 1,
Print["divisible by "<>i]]]; Print["prime test passed; call Lucas and Lehmer"]</
=={{header|Maxima}}==
<
while mod(m, 2 * k * p + 1) # 0 do k: k + 1,
2 * k * p + 1
Line 1,649 ⟶ 1,997:
mersenne_fac(929);
/* 13007 */</
=={{header|Nim}}==
{{trans|C}}
<
proc isPrime(a: int): bool =
Line 1,678 ⟶ 2,026:
if i != 1: d += 2 * q
else: break
echo "2^",q," - 1 = 0 (mod ",d,")"</
{{out}}
<pre>2^929 - 1 = 0 (mod 13007)</pre>
Line 1,687 ⟶ 2,035:
(GNU Octave has a <code>isprime</code> built-in test)
<
function b = bittst(n, p)
b = bitand(n, 2^(p-1)) > 0;
Line 1,720 ⟶ 2,068:
endfunction
printf("%d\n", Mfactor(929));</
=={{header|PARI/GP}}==
This version takes about 15 microseconds to find a factor of 2<sup>929</sup> − 1.
<
forstep(q=2*p+1,sqrt(2)<<(p\2),2*p,
[1,0,0,0,0,0,1][q%8] && Mod(2, q)^p==1 && return(q)
Line 1,730 ⟶ 2,078:
1<<p-1
};
factorMersenne(929)</
This implementation seems to be broken:
<
printp("Test TM \t...");
S=2*p+1;
Line 1,752 ⟶ 2,100:
);
return(status);
}</
=={{header|Pascal}}==
{{trans|Fortran}}
<
function isPrime(n: longint): boolean;
Line 1,839 ⟶ 2,187:
else
writeln('M', exponent, ' (2**', exponent, ' - 1) has the factor: ', factor);
end.</
{{out}}
<pre>
Line 1,848 ⟶ 2,196:
=={{header|Perl}}==
<
use utf8;
Line 1,908 ⟶ 2,256:
print $f? "M$m = $x = $q × @{[$x / $q]}\n"
: "M$m = $x is prime\n";
}</
{{out}}
<pre>M2 = 3 is prime
Line 1,923 ⟶ 2,271:
Following the task introduction, this uses GMP's modular exponentiation and simple probable prime test for the small numbers, then looks for small factors before doing a Lucas-Lehmer test. For ranges above about p=2000, looking for small factors this way saves time (the amount of testing should be adjusted based on the input size and platform -- this example just uses a fixed amount). Note as well that the Lucas-Lehmer test shown here is ignoring the large speedup we can get by optimizing the modulo operation, but that's a different task.
<
# Use GMP's simple probable prime test.
Line 1,952 ⟶ 2,300:
print "M$p is ", is_mersenne_prime($p) ? "prime" : "composite", "\n";
}
}</
{{out}}
<pre>
Line 1,982 ⟶ 2,330:
M929 = 13007 * 348890248924[.....]64184273
</pre>
=={{header|Phix}}==
Translation/Amalgamation of BBC BASIC, D, and Go
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">modpow</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">i</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">*</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">z</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">*</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">y</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">mersenne_factor</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">))-</span><span style="color: #000000;">1</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">p</span><span style="color: #0000FF;">*</span><span style="color: #000000;">k</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">limit</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">),{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">and</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">and</span> <span style="color: #000000;">modpow</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">q</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">23</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">29</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">37</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">41</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">43</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">47</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">53</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">59</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">67</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">71</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">73</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">79</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">83</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">97</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">929</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">937</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</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;">"A factor of M%d is %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mersenne_factor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{Out}}
<pre>
Line 2,136 ⟶ 2,396:
{{trans|D}}
Requires bcmath
<
function mersenneFactor($p) {
Line 2,157 ⟶ 2,417:
}
return true;
}</
{{out}}
Line 2,163 ⟶ 2,423:
=={{header|PicoLisp}}==
<
(let M 1
(loop
Line 2,193 ⟶ 2,453:
(prime? Q)
(= 1 (**Mod 2 P Q)) )
Q ) ) ) )</
{{out}}
<pre>: (for P (2 3 4 5 7 11 13 17 19 23 29 31 37 41 43 47 53 929)
Line 2,222 ⟶ 2,482:
=={{header|Prolog}}==
<
mersenne_factor(P, F) :-
prime(P),
Line 2,250 ⟶ 2,510:
N mod D =\= 0,
D2 is D + A, prime(N, D2, As).
</syntaxhighlight>
{{Out}}
<pre>
Line 2,271 ⟶ 2,531:
=={{header|Python}}==
<
return True # code omitted - see Primality by Trial Division
Line 2,295 ⟶ 2,555:
print "No factor found for M%d" % exponent
else:
print "M%d has a factor: %d" % (exponent, factor)</
{{out|Example}}
Line 2,304 ⟶ 2,564:
=={{header|Racket}}==
<
#lang racket
Line 2,325 ⟶ 2,585:
(mersenne-factor 929)
</syntaxhighlight>
{{out}}
<
13007
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>sub mtest($bits, $p) {
my @bits = $bits.base(2).comb;
loop (my $sq = 1; @bits; $sq %= $p) {
$sq ×= $sq;
$sq += $sq if 1 == @bits.shift;
}
$sq == 1;
}
for flat 2 .. 60, 929 -> $m {
next unless is-prime($m);
my $f = 0;
my $x = 2**$m - 1;
my $q;
for 1..* -> $k {
$q = 2 × $k × $m + 1;
next unless $q % 8 == 1|7 or is-prime($q);
last if $q × $q > $x or $f = mtest($m, $q);
}
say $f ?? "M$m = $x\n\t= $q × { $x div $q }"
!! "M$m = $x is prime";
}</syntaxhighlight>
{{out}}
<pre>M2 = 3 is prime
M3 = 7 is prime
M5 = 31 is prime
M7 = 127 is prime
M11 = 2047
= 23 × 89
M13 = 8191 is prime
M17 = 131071 is prime
M19 = 524287 is prime
M23 = 8388607
= 47 × 178481
M29 = 536870911
= 233 × 2304167
M31 = 2147483647 is prime
M37 = 137438953471
= 223 × 616318177
M41 = 2199023255551
= 13367 × 164511353
M43 = 8796093022207
= 431 × 20408568497
M47 = 140737488355327
= 2351 × 59862819377
M53 = 9007199254740991
= 6361 × 1416003655831
M59 = 576460752303423487
= 179951 × 3203431780337
M929 = 4538015467766671944574165338592225830478699345884382504442663144885072806275648112625635725391102144133907238129251016389326737199538896813326509341743147661691195191795226666084858428449394948944821764472508048114220424520501343042471615418544488778723282182172070046459244838911
= 13007 × 348890248924938259750454781163390930305120269538278042934009621348894657205785201247454118966026150852149399410259938217062100192168747352450719561908445272675574320888385228421992652298715687625495638077382028762529439880103124705348782610789919949159935587158612289264184273</pre>
=={{header|REXX}}==
REXX practically has no limit (well, up to around 8 million) on the number of decimal digits (precision).
This REXX version automatically adjusts the '''numeric digits''' to whatever is needed.
<
numeric digits 20 /*this will be increased if necessary. */
parse arg N spec /*obtain optional arguments from the CL*/
if N=='' | N==","
if spec=='' | spec==","
do j=1;
if j==N
if j>word(spec, 2) then leave /*done with
if \isPrime(z) then iterate /*if Z isn't a prime, keep plugging.*/
r= commas( testMer(z) ); L= length(r) /*add commas; get its new length.
if r==0 then say right('M'z, 10) "──────── is a Mersenne prime."
end /*j*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas:
/*──────────────────────────────────────────────────────────────────────────────────────*/
isPrime: procedure; parse arg x; if wordpos(x, '2 3 5 7') \== 0 then return 1
Line 2,359 ⟶ 2,674:
end /*j*/ /* └─◄ Is j>√ x ? Then return 1*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
iSqrt: procedure; parse arg x;
do while #>1; #= # % 4; _= x-r-#; r= r % 2
if _>=0 then do; x= _; r= r + #
end
end /*while*/ /*iSqrt ≡ integer square root.*/
return r /*───── ─ ── ─ ─ */
/*──────────────────────────────────────────────────────────────────────────────────────*/
testMer: procedure; parse arg x; p= 2**x
$$=x2b( d2x(x) ) + 0
if pos('E',p)\==0 then do; parse var p "E" _; numeric digits _ + 2; p= 2**x
R= iSqrt(p)
if q//
if q// 7==0 then iterate /* " " seven? */
if q//11==0 then iterate /* " " eleven?*/
/* ____ */
if q>R then return 0 /*Is q>√2**x ? A Mersenne prime*/
sq= 1;
do until $==''; sq= sq*sq
parse var $ _ 2 $ /*obtain 1st digit and the rest. */
if _ then sq= (sq+sq) // q
end /*until*/
if sq==1 then return q /*Not a prime? Return a factor.*/
end /*k*/</
Program note: the '''iSqrt''' function computes the integer square root of a non-negative integer without using any floating point, just integers.
Line 2,391 ⟶ 2,712:
M5 ──────── is a Mersenne prime.
M7 ──────── is a Mersenne prime.
M11 is composite, a factor: 23
M13 ──────── is a Mersenne prime.
M17 ──────── is a Mersenne prime.
M19 ──────── is a Mersenne prime.
M23 is composite, a factor: 47
M29 is composite, a factor: 233
M31 ──────── is a Mersenne prime.
M37 is composite, a factor: 223
M41 is composite, a factor: 13,367
M43 is composite, a factor: 431
M47 is composite, a factor: 2,351
M53 is composite, a factor: 6,361
M59 is composite, a factor: 179,951
M61 ──────── is a Mersenne prime.
M67 is composite, a factor: 193,707,721
M71 is composite, a factor: 228,479
M73 is composite, a factor: 439
M79 is composite, a factor: 2,687
M83 is composite, a factor: 167
M929 is composite, a factor: 13,007
M937 is composite, a factor: 28,111
M941 is composite, a factor: 7,529
M947 is composite, a factor: 295,130,657
M953 is composite, a factor: 343,081
M967 is composite, a factor: 23,209
</pre>
=={{header|Ring}}==
<
# Project : Factors of a Mersenne number
Line 2,461 ⟶ 2,782:
end
return y
</syntaxhighlight>
Output:
<pre>
Line 2,467 ⟶ 2,788:
A factor of M937 is 28111
</pre>
=={{header|RPL}}==
{{works with|HP|48}}
<code>PRIM?</code> is defined at [[Primality by trial division#RPL|Primality by trial division]]
{| class="wikitable" ≪
! RPL code
! Comment
|-
|
≪ SWAP R→B → quotient power
≪ 2 power B→R LN 2 LN / FLOOR ^ R→B
1
'''WHILE''' OVER B→R '''REPEAT'''
SQ
'''IF''' OVER power AND B→R '''THEN''' DUP + '''END'''
quotient MOD
SWAP SR SWAP
'''END''' SWAP DROP
≫ ≫ '<span style="color:blue">MODPOW</span>' STO
≪ 2 OVER ^ 1 - √ 0 → power max k
≪ 1
'''WHILE''' 'k' INCR 2 * 1 + DUP max ≤ '''REPEAT'''
'''IF''' { 1 7 } OVER 8 MOD POS THEN
'''IF''' DUP <span style="color:blue">PRIM?</span> THEN
'''IF''' power OVER <span style="color:blue">MODPOW</span> 1 == '''THEN'''
SWAP max 'k' STO '''END'''
'''END END'''
DROP
'''END''' DROP
≫ '<span style="color:blue">MFACT</span>' STO
|
<span style="color:blue">MODPOW</span> ''( power quotient → remainder )''
create top-bit mask
square = 1
while mask is not zero
square *= square
if unmasked bit = 1 then square += square
square = square mod quotient
shift mask right
clean stack
return square
<span style="color:blue">MFACT</span> ''( N → factor ) ''
factor = 1
while 2k+1 ≤ sqrt(M(N))
if 2k+1 mod 8 is equal to 1 or 7
if 2k+1 prime
is 2K+1 a factor of M(N) ?
if yes, exit loop
return factor
|}
929 <span style="color:blue">MFACT</span>
{{out}}
<pre>
1: 13007
</pre>
Factor found in 69 minutes on a 4-bit HP-48SX calculator.
=={{header|Ruby}}==
{{works with|Ruby|1.9.3+}}
<
def mersenne_factor(p)
Line 2,503 ⟶ 2,885:
Prime.each(53) { |p| check_mersenne p }
check_mersenne 929</
{{out}}
Line 2,523 ⟶ 2,905:
M53 = 2**53-1 is composite with factor 6361
M929 = 2**929-1 is composite with factor 13007</pre>
=={{header|Rust}}==
{{trans|C++}}
<syntaxhighlight lang="rust">fn bit_count(mut n: usize) -> usize {
let mut count = 0;
while n > 0 {
n >>= 1;
count += 1;
}
count
}
fn mod_pow(p: usize, n: usize) -> usize {
let mut square = 1;
let mut bits = bit_count(p);
while bits > 0 {
square = square * square;
bits -= 1;
if (p & (1 << bits)) != 0 {
square <<= 1;
}
square %= n;
}
return square;
}
fn is_prime(n: usize) -> bool {
if n < 2 {
return false;
}
if n % 2 == 0 {
return n == 2;
}
if n % 3 == 0 {
return n == 3;
}
let mut p = 5;
while p * p <= n {
if n % p == 0 {
return false;
}
p += 2;
if n % p == 0 {
return false;
}
p += 4;
}
true
}
fn find_mersenne_factor(p: usize) -> usize {
let mut k = 0;
loop {
k += 1;
let q = 2 * k * p + 1;
if q % 8 == 1 || q % 8 == 7 {
if mod_pow(p, q) == 1 && is_prime(p) {
return q;
}
}
}
}
fn main() {
println!("{}", find_mersenne_factor(929));
}</syntaxhighlight>
{{out}}
<pre>
13007
</pre>
=={{header|Scala}}==
Line 2,528 ⟶ 2,981:
===Full-blown version===
<syntaxhighlight lang="scala">
/** Find factors of a Mersenne number
*
Line 2,567 ⟶ 3,020:
(primes takeWhile (_ <= 97)) ++ List(929, 937) foreach { p => { // Needs some intermediate results for nice formatting
val nMersenne = mersenne(p);
val lit =
val preAmble = f"${s"M${p}"}%4s = 2^$p%03d - 1 = ${lit}%s"
Line 2,588 ⟶ 3,041:
}
}
</syntaxhighlight>
{{out}}
<pre style="height:40ex;overflow:scroll"> M2 = 2^002 - 1 = 3 is a Mersenne prime number. (63 msec)
Line 2,640 ⟶ 3,093:
This works with PLT Scheme, other implementations only need to change the inclusion.
<
#lang scheme
Line 2,662 ⟶ 3,115:
(= 1 (modpow p i))))
i))
</syntaxhighlight>
{{out}}
<pre>
Line 2,674 ⟶ 3,127:
=={{header|Seed7}}==
<
const func boolean: isPrime (in integer: number) is func
Line 2,737 ⟶ 3,190:
begin
writeln("Factor of M929: " <& mersenneFactor(929));
end func;</
Original source: [http://seed7.sourceforge.net/algorith/math.htm#isPrime isPrime],
Line 2,748 ⟶ 3,201:
=={{header|Sidef}}==
<
var bits = b.base(2).digits
for (var sq = 1; bits; sq %= p) {
Line 2,768 ⟶ 3,221:
say (f ? "M#{m} is composite with factor #{q}"
: "M#{m} is prime")
}</
{{out}}
<pre>
Line 2,793 ⟶ 3,246:
=={{header|Swift}}==
<
extension BinaryInteger {
Line 2,855 ⟶ 3,308:
print(mFactor(exp: 929)!)
</syntaxhighlight>
{{out}}
Line 2,863 ⟶ 3,316:
=={{header|Tcl}}==
For <code>primes::is_prime</code> see [[Prime decomposition#Tcl]]
<
binary scan [binary format I1 $n] B* binstring
return [split [string trimleft $binstring 0] ""]
Line 2,907 ⟶ 3,360:
} else {
puts "no factor found for M$exp"
}</
=={{header|TI-83 BASIC}}==
Line 2,913 ⟶ 3,366:
{{works with|TI-83 BASIC|TI-84Plus 2.55MP}}
The program uses the new remainder function from OS 2.53MP, if not available it can be replaced by:
<
<
1→K:0→T
While K≤2^20 and T=0
Line 2,946 ⟶ 3,399:
End
If T=0:0→F
Disp Q,F</
{{in}}
<pre>
Line 2,959 ⟶ 3,412:
=={{header|uBasic/4tH}}==
<syntaxhighlight lang="text">Print "A factor of M929 is "; FUNC(_FNmersenne_factor(929))
Print "A factor of M937 is "; FUNC(_FNmersenne_factor(937))
Line 3,012 ⟶ 3,465:
Next
Return (d@)</
{{out}}
<pre>A factor of M929 is 13007
Line 3,021 ⟶ 3,474:
=={{header|VBScript}}==
{{trans|REXX}}
<
for i=1 to 59
z=i
Line 3,083 ⟶ 3,536:
loop
testM=0
end function</
{{out}}
<pre>
Line 3,108 ⟶ 3,561:
{{trans|BBC BASIC}}
{{works with|Visual Basic|VB6 Standard}}
<
Dim q As Long, k As Long, p As Long, d As Long
Dim factor As Long, i As Long, y As Long, z As Long
Line 3,143 ⟶ 3,596:
okfactor:
Debug.Print "M" & q, "factor=" & factor
End Sub</
{{Out}}
<pre>
M47 factor=2351
</pre>
=={{header|V (Vlang)}}==
{{trans|go}}
<syntaxhighlight lang="go">import math
const qlimit = int(2e8)
fn main() {
mtest(31)
mtest(67)
mtest(929)
}
fn mtest(m int) {
// the function finds odd prime factors by
// searching no farther than sqrt(N), where N = 2^m-1.
// the first odd prime is 3, 3^2 = 9, so M3 = 7 is still too small.
// M4 = 15 is first number for which test is meaningful.
if m < 4 {
println("$m < 4. M$m not tested.")
return
}
flimit := math.sqrt(math.pow(2, f64(m)) - 1)
mut qlast := 0
if flimit < qlimit {
qlast = int(flimit)
} else {
qlast = qlimit
}
mut composite := []bool{len: qlast+1}
sq := int(math.sqrt(f64(qlast)))
loop:
for q := int(3); ; {
if q <= sq {
for i := q * q; i <= qlast; i += q {
composite[i] = true
}
}
q8 := q % 8
if (q8 == 1 || q8 == 7) && mod_pow(2, m, q) == 1 {
println("M$m has factor $q")
return
}
for {
q += 2
if q > qlast {
break loop
}
if !composite[q] {
break
}
}
}
println("No factors of M$m found.")
}
// base b to power p, mod m
fn mod_pow(b int, p int, m int) int {
mut pow := i64(1)
b64 := i64(b)
m64 := i64(m)
mut bit := u32(30)
for 1<<bit&p == 0 {
bit--
}
for {
pow *= pow
if 1<<bit&p != 0 {
pow *= b64
}
pow %= m64
if bit == 0 {
break
}
bit--
}
return int(pow)
}</syntaxhighlight>
{{out}}
<pre>
No factors of M31 found.
M67 has factor 193707721
M929 has factor 13007
</pre>
=={{header|Wren}}==
{{trans|JavaScript}}
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./math" for Int
import "./fmt" for Conv, Fmt
var trialFactor = Fn.new { |base, exp, mod|
var square = 1
var bits = Conv.itoa(exp, 2).toList
var ln = bits.count
for (i in 0...ln) {
square = square * square * (bits[i] == "1" ? base : 1) % mod
}
return square == 1
}
var mersenneFactor = Fn.new { |p|
var limit = (2.pow(p) - 1).sqrt.floor
var k = 1
while ((2*k*p - 1) < limit) {
var q = 2*k*p + 1
if (Int.isPrime(q) && (q%8 == 1 || q%8 == 7) && trialFactor.call(2, p, q)) {
return q // q is a factor of 2^p - 1
}
k = k + 1
}
return null
}
var m = [3, 5, 11, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 67, 71, 73, 79, 83, 97, 929]
for (p in m) {
var f = mersenneFactor.call(p)
Fmt.write("2^$3d - 1 is ", p)
if (f) {
Fmt.print("composite (factor $d)", f)
} else {
System.print("prime")
}
}</syntaxhighlight>
{{out}}
<pre>
2^ 3 - 1 is prime
2^ 5 - 1 is prime
2^ 11 - 1 is composite (factor 23)
2^ 17 - 1 is prime
2^ 23 - 1 is composite (factor 47)
2^ 29 - 1 is composite (factor 233)
2^ 31 - 1 is prime
2^ 37 - 1 is composite (factor 223)
2^ 41 - 1 is composite (factor 13367)
2^ 43 - 1 is composite (factor 431)
2^ 47 - 1 is composite (factor 2351)
2^ 53 - 1 is composite (factor 6361)
2^ 59 - 1 is composite (factor 179951)
2^ 67 - 1 is composite (factor 193707721)
2^ 71 - 1 is composite (factor 228479)
2^ 73 - 1 is composite (factor 439)
2^ 79 - 1 is composite (factor 2687)
2^ 83 - 1 is composite (factor 167)
2^ 97 - 1 is composite (factor 11447)
2^929 - 1 is composite (factor 13007)
</pre>
=={{header|zkl}}==
{{trans|EchoLisp}}
<
// M = 2^P - 1 , P prime
Line 3,167 ⟶ 3,768:
}
False
}</
<
m_divisor(4423).println(); // False
(BN(2).pow(4423) - 1).probablyPrime().println(); // True</
{{out}}
<pre>
|