Factors of a Mersenne number: Difference between revisions
Content added Content deleted
No edit summary |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
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,084:
=={{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:
→ #t
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Ruby}}
<
def mersenne_factor(p) do
limit = :math.sqrt(:math.pow(2, p) - 1)
Line 1,147:
[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:
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:
false -> divisors(N, C-1)
end.
</syntaxhighlight>
{{out}}
<pre>
Line 1,232:
=={{header|Factor}}==
<
math math.bits math.functions math.primes sequences ;
IN: rosetta-code.mersenne-factors
Line 1,263:
[ [I No factor found for M${}.I] ] if* nl ;
929 test-mersenne</
{{out}}
<pre>
Line 1,270:
=={{header|Forth}}==
<
3
begin 2dup dup * >=
Line 1,302:
929 factor-mersenne . \ 13007
4423 factor-mersenne . \ 0</
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
IMPLICIT NONE
INTEGER :: exponent, factor
Line 1,357:
Mfactor = 0
END FUNCTION
END PROGRAM EXAMPLE</
{{out}}
M929 has a factor: 13007
Line 1,363:
=={{header|FreeBASIC}}==
{{trans|C}}
<
Function isPrime(n As Integer) As Boolean
Line 1,407:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 1,431:
=={{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:
=={{header|GAP}}==
<
local k, m, d;
if IsPrime(n) then
Line 1,471:
FactorsInt(2^101-1);
# [ 7432339208719, 341117531003194129 ]</
=={{header|Go}}==
<
import (
Line 1,554:
}
return int32(pow)
}</
{{out}}
<pre>
Line 1,566:
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:
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:
The following works in both languages:
<
p := integer(A[1]) | 929
write("M",p," has a factor ",mfactor(p))
Line 1,618:
}
return
end</
Sample runs:
Line 1,631:
=={{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:
}
</syntaxhighlight>
{{out}}
Line 1,739:
=={{header|JavaScript}}==
<
var limit, k, q
limit = Math.sqrt(Math.pow(2,p) - 1)
Line 1,779:
f = mersenne_factor(p)
console.log(f == null ? "prime" : "composite with factor "+f)
}</
<pre>
Line 1,791:
=={{header|Julia}}==
<
using Primes
Line 1,811:
if mf != -1 println("M$i = ", mf, " × ", (big(2) ^ i - 1) ÷ mf)
else println("M$i is prime") end
end</
{{out}}
Line 1,829:
=={{header|Kotlin}}==
{{trans|C}}
<
fun isPrime(n: Int): Boolean {
Line 1,875:
}
}
}</
{{out}}
Line 1,898:
=={{header|Lingo}}==
<
bits = getBits(e)
sq = 1
Line 1,920:
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:
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:
mersenne_fac(929);
/* 13007 */</
=={{header|Nim}}==
{{trans|C}}
<
proc isPrime(a: int): bool =
Line 1,977:
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:
(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:
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:
1<<p-1
};
factorMersenne(929)</
This implementation seems to be broken:
<
printp("Test TM \t...");
S=2*p+1;
Line 2,051:
);
return(status);
}</
=={{header|Pascal}}==
{{trans|Fortran}}
<
function isPrime(n: longint): boolean;
Line 2,138:
else
writeln('M', exponent, ' (2**', exponent, ' - 1) has the factor: ', factor);
end.</
{{out}}
<pre>
Line 2,147:
=={{header|Perl}}==
<
use utf8;
Line 2,207:
print $f? "M$m = $x = $q × @{[$x / $q]}\n"
: "M$m = $x is prime\n";
}</
{{out}}
<pre>M2 = 3 is prime
Line 2,222:
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:
print "M$p is ", is_mersenne_prime($p) ? "prime" : "composite", "\n";
}
}</
{{out}}
<pre>
Line 2,284:
=={{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:
<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:
{{trans|D}}
Requires bcmath
<
function mersenneFactor($p) {
Line 2,368:
}
return true;
}</
{{out}}
Line 2,374:
=={{header|PicoLisp}}==
<
(let M 1
(loop
Line 2,404:
(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:
=={{header|Prolog}}==
<
mersenne_factor(P, F) :-
prime(P),
Line 2,461:
N mod D =\= 0,
D2 is D + A, prime(N, D2, As).
</syntaxhighlight>
{{Out}}
<pre>
Line 2,482:
=={{header|Python}}==
<
return True # code omitted - see Primality by Trial Division
Line 2,506:
print "No factor found for M%d" % exponent
else:
print "M%d has a factor: %d" % (exponent, factor)</
{{out|Example}}
Line 2,515:
=={{header|Racket}}==
<
#lang racket
Line 2,536:
(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:
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:
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:
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:
=={{header|Ring}}==
<
# Project : Factors of a Mersenne number
Line 2,733:
end
return y
</syntaxhighlight>
Output:
<pre>
Line 2,742:
=={{header|Ruby}}==
{{works with|Ruby|1.9.3+}}
<
def mersenne_factor(p)
Line 2,775:
Prime.each(53) { |p| check_mersenne p }
check_mersenne 929</
{{out}}
Line 2,798:
=={{header|Rust}}==
{{trans|C++}}
<
let mut count = 0;
while n > 0 {
Line 2,860:
fn main() {
println!("{}", find_mersenne_factor(929));
}</
{{out}}
Line 2,871:
===Full-blown version===
<syntaxhighlight lang="scala">
/** Find factors of a Mersenne number
*
Line 2,931:
}
}
</syntaxhighlight>
{{out}}
<pre style="height:40ex;overflow:scroll"> M2 = 2^002 - 1 = 3 is a Mersenne prime number. (63 msec)
Line 2,983:
This works with PLT Scheme, other implementations only need to change the inclusion.
<
#lang scheme
Line 3,005:
(= 1 (modpow p i))))
i))
</syntaxhighlight>
{{out}}
<pre>
Line 3,017:
=={{header|Seed7}}==
<
const func boolean: isPrime (in integer: number) is func
Line 3,080:
begin
writeln("Factor of M929: " <& mersenneFactor(929));
end func;</
Original source: [http://seed7.sourceforge.net/algorith/math.htm#isPrime isPrime],
Line 3,091:
=={{header|Sidef}}==
<
var bits = b.base(2).digits
for (var sq = 1; bits; sq %= p) {
Line 3,111:
say (f ? "M#{m} is composite with factor #{q}"
: "M#{m} is prime")
}</
{{out}}
<pre>
Line 3,136:
=={{header|Swift}}==
<
extension BinaryInteger {
Line 3,198:
print(mFactor(exp: 929)!)
</syntaxhighlight>
{{out}}
Line 3,206:
=={{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:
} else {
puts "no factor found for M$exp"
}</
=={{header|TI-83 BASIC}}==
Line 3,256:
{{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:
End
If T=0:0→F
Disp Q,F</
{{in}}
<pre>
Line 3,302:
=={{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:
Next
Return (d@)</
{{out}}
<pre>A factor of M929 is 13007
Line 3,364:
=={{header|VBScript}}==
{{trans|REXX}}
<
for i=1 to 59
z=i
Line 3,426:
loop
testM=0
end function</
{{out}}
<pre>
Line 3,451:
{{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:
okfactor:
Debug.Print "M" & q, "factor=" & factor
End Sub</
{{Out}}
<pre>
Line 3,494:
=={{header|Vlang}}==
{{trans|go}}
<
const qlimit = int(2e8)
Line 3,567:
}
return int(pow)
}</
{{out}}
<pre>
Line 3,579:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<
import "/fmt" for Conv, Fmt
Line 3,614:
System.print("prime")
}
}</
{{out}}
Line 3,642:
=={{header|zkl}}==
{{trans|EchoLisp}}
<
// M = 2^P - 1 , P prime
Line 3,658:
}
False
}</
<
m_divisor(4423).println(); // False
(BN(2).pow(4423) - 1).probablyPrime().println(); // True</
{{out}}
<pre>
|