Rosetta Code

Factors of a Mersenne number: Difference between revisions

← Older editNewer edit →
Content deleted Content added
m added a ;See also: section header.
m →‎{{header|REXX}}: simplified program, optimized a function, added wording to the REXX section header..
Line 2,259:
 
=={{header|REXX}}==
REXX practically has no limit (well, up to around 8 million) on the number of decimal digits (precision).
<lang rexx>/*REXX program uses exponent─and─mod operator to test possible Mersenne numbers. */
numeric digits 50020 /*dealingthis will withbe someincreased ginormousif numbersnecessary. */
ifdo zj==611 to 61; then z=929j /*now,process a switcheroorange, 61& then do turnsone intomore 929.#*/▼
 
doif jz==1 to 61; z=j then z=929 /*whennow, Ja reaches 61switcheroo, Z turns into 929.*/
▲ if z==61 then z=929 /*now, a switcheroo, 61 turns into 929.*/
if \isPrime(z) then iterate /*if Z isn't a prime, keep plugging.*/
r=testMer(z) /*If Z is prime, give Z the 3rd degree.*/
Line 2,280 ⟶ 2,279:
iSqrt: procedure; parse arg x; #=1; r=0; do while #<=x; #=#*4; end
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 /*───── ─ ── ─ ─ */
return r
/*──────────────────────────────────────────────────────────────────────────────────────*/
modPow: procedure; parse arg base,n,div; sq=1; $=x2b( d2x(n) ) + 0
Line 2,289 ⟶ 2,288:
return sq
/*──────────────────────────────────────────────────────────────────────────────────────*/
testMer: procedure; parse arg x; p=2**x /* [↓] do we have enough /*test a possible Mersenne prime.digits?*/
sqRoot=iSqrtif pos(2**x'E',p)\==0 then do; parse var p 'E' _; numeric digits _+2; /p=2**iSqrtx; ≡ integer square root.*/end
!.=1; !.1=0; !.7=0 /*───── ─ ── array used for ─a quicker ─test. */
do kR=1;iSqrt(p) q=2*k*x + 1 /* _____ /*obtain integer square root of P*/
if q>sqRoot do k=1; then return 0 /*Is q>√ =2^*k*x ? + 1 /* _____ A Mersenne prime*/
_=q // 8 if q>R then return 0 /*Is q>√ 2^x ? A Mersenne /*obtain the remainder when ÷ 8. prime*/
if _\==1 & _\ m==7q // 8 then iterate /*must be either one or seven /*obtain the remainder when ÷ 8. */
if \isPrime(q) then iterateif !.m then iterate /*QM must be ¬prime?either Then keepone onor lookingseven.*/
if modPow(2,x,q)==1 then return q /*Not a prime? Return a factor.*/
end /*k*/</lang>
Program note: &nbsp; the &nbsp; '''iSqrt''' &nbsp; function computes the integer square root of a non-negative integer without using any floating point, just integers.
 
Retrieved from "https://rosettacode.org/wiki/Factors_of_a_Mersenne_number"