Factors of a Mersenne number: Difference between revisions
add RPL
(→{{header|Vlang}}: Rename "Vlang" in "V (Vlang)") |
(add RPL) |
||
Line 2,739:
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}}==
| |||