Rosetta Code

Factors of a Mersenne number: Difference between revisions

Page Discussion

Factors of a Mersenne number (view source)

Revision as of 07:33, 1 June 2020

300 bytes added ,  4 years ago
m
→‎{{header|REXX}}: added/changed comments and whitespace.
(C++ - no need to use a sieve in this case)
m (→‎{{header|REXX}}: added/changed comments and whitespace.)
Line 2,464:
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.
<lang rexx>/*REXX program uses exponent─and─mod operator to test possible Mersenne numbers. */
numeric digits 20 /*this will be increased if necessary. */
parse arg N spec /*obtain optional arguments from the CL*/
if N=='' | N=="," then N= 88 /*Not specified? Then use the default.*/
if spec=='' | spec=="," then spec= 920 970 /* " " " " " " */
do j=1; z=j z= j /*process a range, & then do onesome more #.*/
if j==N then j=word(spec, 1); then j= word(spec, 1) /*now, use the high range of numbers. */
if j>word(spec, 2) then leave /*done with the high" " " " " range of numbers? */
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 Z is prime, give Z the 3rd degree.*/
if r==0 then say right('M'z, 10) "──────── is a Mersenne prime."
r=commas(r); L=length(r) /*add commas to R; get it's new length.*/
if r==0 then else say right('M'z, 1050) "──────── "is composite, a Mersenne prime.factor:"right(r, max(L, 13) )
else say right('M'z, 50) "is composite, a factor:" right(r, max(L, 11) )
end /*j*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg _; do jc=length(_)-3 to 1 by -3; _=insert(',', _, jc); end; return _
/*──────────────────────────────────────────────────────────────────────────────────────*/
isPrime: procedure; parse arg x; if wordpos(x, '2 3 5 7') \== 0 then return 1
Line 2,489 ⟶ 2,488:
end /*j*/ /* └─◄ Is j>√ x ? Then return 1*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
iSqrt: procedure; parse arg x; #= 1; r= 0; do while #<=x; #= # *4; end4
do while #>1; #=#%4; _=x-r-#; r=r%2; if _>=0 then do; x=_; r=r+#; end /*while*/
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 /* [↓] do we have enough digits?*/
$$=x2b( d2x(x) ) + 0
if pos('E',p)\==0 then do; parse var p "E" _; numeric digits _ + 2; p= 2**x; end
!.=1; !.1=0; !.7=0 /*array used for a quicker test. */end
R!.=iSqrt(p) 1; !.1= 0; !.7= 0 /*obtainarray used integerfor squarea rootquicker oftest. P*/
R= iSqrt(p) do k=2 by 2; q=k*x + 1 /*(shortcut)obtain computeinteger valuesquare ofroot Q.of P*/
mdo k=q // 8 2 by 2; q= k*x + 1 /*obtain the(shortcut) remaindercompute whenvalue ÷of 8Q. */
if !.m= q // 8 then iterate /*M must be either one or seven /*obtain the remainder when ÷ 8. */
parseif var!.m q '' -1 _; if _==5 then iterate /*lastM must digitbe aeither fiveone ?or seven.*/
ifparse var q//3==0 '' then-1 iterate_; if _==5 then iterate /*last digit a five /*divisible by three? */
if q//7 3==0 then iterate /* ____ " /*divisible "by seventhree? */
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; $= $$ /*obtain binary version from $. */
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.*/
Line 2,521 ⟶ 2,526:
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>
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/93064"