Factors of a Mersenne number: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|C sharp}}: Regularize header markup to recommended on category page) |
No edit summary |
||
Line 3,490: | Line 3,490: | ||
<pre> |
<pre> |
||
M47 factor=2351 |
M47 factor=2351 |
||
</pre> |
|||
=={{header|Vlang}}== |
|||
{{trans|go}} |
|||
<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) |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
No factors of M31 found. |
|||
M67 has factor 193707721 |
|||
M929 has factor 13007 |
|||
</pre> |
</pre> |
||