Factors of a Mersenne number: Difference between revisions
Added Easylang
m (→{{header|Phix}}: added syntax colouring, marked p2js compatible) |
(Added Easylang) |
||
(6 intermediate revisions by 5 users not shown) | |||
Line 63:
{{trans|Python}}
<
I a == 2 {R 1B}
I a < 2 | a % 2 == 0 {R 0B}
Line 91:
print(‘No factor found for M#.’.format(exponent))
E
print(‘M#. has a factor: #.’.format(exponent, factor))</
{{out}}
Line 101:
=={{header|8086 Assembly}}==
<
cpu 8086
bits 16
Line 194:
factor: db "Found factor: $"
prcnt: dw 2 ; Amount of primes currently in list
primes: dw 2, 3 ; List of primes to be extended</
{{out}}
Line 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 293:
PG DS CL24 buffer
YREGS
END MERSENNE</
{{out}}
<pre>
Line 301:
=={{header|Ada}}==
mersenne.adb:
<
-- reuse Is_Prime from [[Primality by Trial Division]]
with Is_Prime;
Line 368:
Ada.Text_IO.Put_Line ("is not a Mersenne number");
end;
end Mersenne;</
{{out}}
Line 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 430:
FI
END</
Example:
<pre>
Line 439:
=={{header|Arturo}}==
<
if not? prime? q -> print "number not prime!"
r: new q
Line 460:
]
mersenneFactors 929</
{{out}}
Line 468:
=={{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 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 563:
ENDWHILE
= Y%
</syntaxhighlight>
{{out}}
<pre>A factor of M929 is 13007
Line 569:
=={{header|Bracmat}}==
<
= square P divisor highbit log 2pow
. !arg:(?P.?divisor)
Line 630:
| out$"no divisors found"
)
);</
{{out}}
<pre>found some divisors of 2^!P-1 : 13007 and 348890248924938259750454781163390930305120269538278042934009621348894657205785
Line 638:
=={{header|C}}==
<
if (n%2==0) return n==2;
if (n%3==0) return n==3;
Line 661:
else break;
} while(1);
printf("2^%d - 1 = 0 (mod %d)\n", q, d);}</
=={{header|C sharp|C#}}==
<
namespace prog
Line 709:
}
}
}</
=={{header|C++}}==
<
#include <cstdint>
Line 757:
std::cout << find_mersenne_factor(929) << std::endl;
return 0;
}</
{{out}}
Line 767:
{{trans|Python}}
<
(:gen-class))
Line 825:
:let [s (-main p)]]
(println s))
</syntaxhighlight>
{{Output}}
<pre>
Line 853:
{{trans|Ruby}}
<
limit = Math.sqrt(Math.pow(2,p) - 1)
k = 1
Line 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 904:
=={{header|Common Lisp}}==
{{trans|Maxima}}
<
(loop for k from 1
for n = (1+ (* 2 k p))
Line 910:
finally (return n)))
(print (mersenne-fac 929))</
{{out}}
Line 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 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 976:
=={{header|Crystal}}==
{{trans|Ruby}}
<
def prime?(n) # P3 Prime Generator primality test
Line 1,018:
(2..53).each { |p| check_mersenne(p) if prime?(p) }
check_mersenne 929</
{{out}}
Line 1,040:
=={{header|D}}==
<
ulong mersenneFactor(in ulong p) pure nothrow @nogc {
Line 1,076:
void main() {
writefln("Factor of M929: %d", 929.mersenneFactor);
}</
{{out}}
<pre>Factor of M929: 13007</pre>
Line 1,082:
=={{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 1,108 ⟶ 1,157:
→ #t
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Ruby}}
<
def mersenne_factor(p) do
limit = :math.sqrt(:math.pow(2, p) - 1)
Line 1,147 ⟶ 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 1,174 ⟶ 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 1,217 ⟶ 1,266:
false -> divisors(N, C-1)
end.
</syntaxhighlight>
{{out}}
<pre>
Line 1,232 ⟶ 1,281:
=={{header|Factor}}==
<
math math.bits math.functions math.primes sequences ;
IN: rosetta-code.mersenne-factors
Line 1,263 ⟶ 1,312:
[ [I No factor found for M${}.I] ] if* nl ;
929 test-mersenne</
{{out}}
<pre>
Line 1,270 ⟶ 1,319:
=={{header|Forth}}==
<
3
begin 2dup dup * >=
Line 1,302 ⟶ 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,357 ⟶ 1,406:
Mfactor = 0
END FUNCTION
END PROGRAM EXAMPLE</
{{out}}
M929 has a factor: 13007
Line 1,363 ⟶ 1,412:
=={{header|FreeBASIC}}==
{{trans|C}}
<
Function isPrime(n As Integer) As Boolean
Line 1,407 ⟶ 1,456:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 1,431 ⟶ 1,480:
=={{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.
<
if modPow[2, 929, p] - 1 == 0
println[p]</
{{out}}
<pre>
Line 1,440 ⟶ 1,489:
=={{header|GAP}}==
<
local k, m, d;
if IsPrime(n) then
Line 1,471 ⟶ 1,520:
FactorsInt(2^101-1);
# [ 7432339208719, 341117531003194129 ]</
=={{header|Go}}==
<
import (
Line 1,554 ⟶ 1,603:
}
return int32(pow)
}</
{{out}}
<pre>
Line 1,566 ⟶ 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,578 ⟶ 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,587 ⟶ 1,636:
The following works in both languages:
<
p := integer(A[1]) | 929
write("M",p," has a factor ",mfactor(p))
Line 1,618 ⟶ 1,667:
}
return
end</
Sample runs:
Line 1,631 ⟶ 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,712 ⟶ 1,761:
}
</syntaxhighlight>
{{out}}
Line 1,739 ⟶ 1,788:
=={{header|JavaScript}}==
<
var limit, k, q
limit = Math.sqrt(Math.pow(2,p) - 1)
Line 1,779 ⟶ 1,828:
f = mersenne_factor(p)
console.log(f == null ? "prime" : "composite with factor "+f)
}</
<pre>
Line 1,791 ⟶ 1,840:
=={{header|Julia}}==
<
using Primes
Line 1,811 ⟶ 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,829 ⟶ 1,878:
=={{header|Kotlin}}==
{{trans|C}}
<
fun isPrime(n: Int): Boolean {
Line 1,875 ⟶ 1,924:
}
}
}</
{{out}}
Line 1,898 ⟶ 1,947:
=={{header|Lingo}}==
<
bits = getBits(e)
sq = 1
Line 1,920 ⟶ 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,937 ⟶ 1,986:
Believe it or not, this type of test runs faster in Mathematica than the squaring version described above.
<
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,948 ⟶ 1,997:
mersenne_fac(929);
/* 13007 */</
=={{header|Nim}}==
{{trans|C}}
<
proc isPrime(a: int): bool =
Line 1,977 ⟶ 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,986 ⟶ 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 2,019 ⟶ 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 2,029 ⟶ 2,078:
1<<p-1
};
factorMersenne(929)</
This implementation seems to be broken:
<
printp("Test TM \t...");
S=2*p+1;
Line 2,051 ⟶ 2,100:
);
return(status);
}</
=={{header|Pascal}}==
{{trans|Fortran}}
<
function isPrime(n: longint): boolean;
Line 2,138 ⟶ 2,187:
else
writeln('M', exponent, ' (2**', exponent, ' - 1) has the factor: ', factor);
end.</
{{out}}
<pre>
Line 2,147 ⟶ 2,196:
=={{header|Perl}}==
<
use utf8;
Line 2,207 ⟶ 2,256:
print $f? "M$m = $x = $q × @{[$x / $q]}\n"
: "M$m = $x is prime\n";
}</
{{out}}
<pre>M2 = 3 is prime
Line 2,222 ⟶ 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 2,251 ⟶ 2,300:
print "M$p is ", is_mersenne_prime($p) ? "prime" : "composite", "\n";
}
}</
{{out}}
<pre>
Line 2,284 ⟶ 2,333:
=={{header|Phix}}==
Translation/Amalgamation of BBC BASIC, D, and Go
<!--<
<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>
Line 2,322 ⟶ 2,371:
<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>
<!--</
{{Out}}
<pre>
Line 2,347 ⟶ 2,396:
{{trans|D}}
Requires bcmath
<
function mersenneFactor($p) {
Line 2,368 ⟶ 2,417:
}
return true;
}</
{{out}}
Line 2,374 ⟶ 2,423:
=={{header|PicoLisp}}==
<
(let M 1
(loop
Line 2,404 ⟶ 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,433 ⟶ 2,482:
=={{header|Prolog}}==
<
mersenne_factor(P, F) :-
prime(P),
Line 2,461 ⟶ 2,510:
N mod D =\= 0,
D2 is D + A, prime(N, D2, As).
</syntaxhighlight>
{{Out}}
<pre>
Line 2,482 ⟶ 2,531:
=={{header|Python}}==
<
return True # code omitted - see Primality by Trial Division
Line 2,506 ⟶ 2,555:
print "No factor found for M%d" % exponent
else:
print "M%d has a factor: %d" % (exponent, factor)</
{{out|Example}}
Line 2,515 ⟶ 2,564:
=={{header|Racket}}==
<
#lang racket
Line 2,536 ⟶ 2,585:
(mersenne-factor 929)
</syntaxhighlight>
{{out}}
<
13007
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
my @bits = $bits.base(2).comb;
loop (my $sq = 1; @bits; $sq %= $p) {
Line 2,567 ⟶ 2,616:
say $f ?? "M$m = $x\n\t= $q × { $x div $q }"
!! "M$m = $x is prime";
}</
{{out}}
<pre>M2 = 3 is prime
Line 2,602 ⟶ 2,651:
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*/
Line 2,654 ⟶ 2,703:
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,691 ⟶ 2,740:
=={{header|Ring}}==
<
# Project : Factors of a Mersenne number
Line 2,733 ⟶ 2,782:
end
return y
</syntaxhighlight>
Output:
<pre>
Line 2,739 ⟶ 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,775 ⟶ 2,885:
Prime.each(53) { |p| check_mersenne p }
check_mersenne 929</
{{out}}
Line 2,798 ⟶ 2,908:
=={{header|Rust}}==
{{trans|C++}}
<
let mut count = 0;
while n > 0 {
Line 2,860 ⟶ 2,970:
fn main() {
println!("{}", find_mersenne_factor(929));
}</
{{out}}
Line 2,871 ⟶ 2,981:
===Full-blown version===
<syntaxhighlight lang="scala">
/** Find factors of a Mersenne number
*
Line 2,931 ⟶ 3,041:
}
}
</syntaxhighlight>
{{out}}
<pre style="height:40ex;overflow:scroll"> M2 = 2^002 - 1 = 3 is a Mersenne prime number. (63 msec)
Line 2,983 ⟶ 3,093:
This works with PLT Scheme, other implementations only need to change the inclusion.
<
#lang scheme
Line 3,005 ⟶ 3,115:
(= 1 (modpow p i))))
i))
</syntaxhighlight>
{{out}}
<pre>
Line 3,017 ⟶ 3,127:
=={{header|Seed7}}==
<
const func boolean: isPrime (in integer: number) is func
Line 3,080 ⟶ 3,190:
begin
writeln("Factor of M929: " <& mersenneFactor(929));
end func;</
Original source: [http://seed7.sourceforge.net/algorith/math.htm#isPrime isPrime],
Line 3,091 ⟶ 3,201:
=={{header|Sidef}}==
<
var bits = b.base(2).digits
for (var sq = 1; bits; sq %= p) {
Line 3,111 ⟶ 3,221:
say (f ? "M#{m} is composite with factor #{q}"
: "M#{m} is prime")
}</
{{out}}
<pre>
Line 3,136 ⟶ 3,246:
=={{header|Swift}}==
<
extension BinaryInteger {
Line 3,198 ⟶ 3,308:
print(mFactor(exp: 929)!)
</syntaxhighlight>
{{out}}
Line 3,206 ⟶ 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 3,250 ⟶ 3,360:
} else {
puts "no factor found for M$exp"
}</
=={{header|TI-83 BASIC}}==
Line 3,256 ⟶ 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 3,289 ⟶ 3,399:
End
If T=0:0→F
Disp Q,F</
{{in}}
<pre>
Line 3,302 ⟶ 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,355 ⟶ 3,465:
Next
Return (d@)</
{{out}}
<pre>A factor of M929 is 13007
Line 3,364 ⟶ 3,474:
=={{header|VBScript}}==
{{trans|REXX}}
<
for i=1 to 59
z=i
Line 3,426 ⟶ 3,536:
loop
testM=0
end function</
{{out}}
<pre>
Line 3,451 ⟶ 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,486 ⟶ 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>
Line 3,496 ⟶ 3,689:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<
import "./fmt" for Conv, Fmt
var trialFactor = Fn.new { |base, exp, mod|
Line 3,531 ⟶ 3,724:
System.print("prime")
}
}</
{{out}}
Line 3,559 ⟶ 3,752:
=={{header|zkl}}==
{{trans|EchoLisp}}
<
// M = 2^P - 1 , P prime
Line 3,575 ⟶ 3,768:
}
False
}</
<
m_divisor(4423).println(); // False
(BN(2).pow(4423) - 1).probablyPrime().println(); // True</
{{out}}
<pre>
|