Fermat numbers: Difference between revisions
→{{header|Wren}}: Now uses BigInt.
Thundergnat (talk | contribs) (→{{header|Ring}}: Incorrect) |
(→{{header|Wren}}: Now uses BigInt.) |
||
Line 2,209:
=={{header|Wren}}==
{{libheader|Wren-
The first seven Fermat numbers are factorized in about 0.75 seconds by Pollard's Rho but as it would take 'hours' to get any further I've stopped there.
<lang ecmascript>import "/
var fermat = Fn.new { |n|
var pollardRho = Fn.new { |n|
for (i in 0..5) {▼
var
var
var
var z = BigInt.one
System.print("F%(String.fromCodePoint(0x2080+i)): %(n) -> factors = %(pf) -> %(kind)")▼
var d = BigInt.one
var count = 0
while (true) {
x = g.call(x, n)
y = g.call(g.call(y, n), n)
d = (x - y).abs % n
z = z * d
count = count + 1
if (count == 100) {
d = BigInt.gcd(z, n)
if (d != BigInt.one) break
z = BigInt.one
count = 0
}
}
if (d == n) return BigInt.zero
return d
}
var primeFactors = Fn.new { |n|
if (n.isProbablePrime(5)) return [n, BigInt.one]
var factor1 = pollardRho.call(n)
var factor2 = n / factor1
return [factor1, factor2]
}
var fns = List.filled(10, null)
System.print("The first 10 Fermat numbers are:")
fns[i] = fermat.call(i)
}
System.print("\nFactors of the first 7 Fermat numbers:")
for (i in 0..6) {
System.write("F%(String.fromCodePoint(0x2080+i)) = ")
var factors = primeFactors.call(fns[i])
System.write("%(factors)")
if (factors[1] == BigInt.one) {
System.print(" (prime)")
} else if (!factors[1].isProbablePrime(5)) {
System.print(" (second factor is composite)")
} else {
System.print()
}
}</lang>
{{out}}
<pre>
The first 10 Fermat numbers are:
F₀: 3 -> factors = [3] -> prime▼
F₀ = 3
F₁: 5 -> factors = [5] -> prime▼
F₁ = 5
F₂: 17 -> factors = [17] -> prime▼
F₂ = 17
F₃: 257 -> factors = [257] -> prime▼
F₃ = 257
F₄: 65537 -> factors = [65537] -> prime▼
F₄ = 65537
F₅ = 4294967297
F₆ = 18446744073709551617
F₇ = 340282366920938463463374607431768211457
F₈ = 115792089237316195423570985008687907853269984665640564039457584007913129639937
F₉ = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097
Factors of the first 7 Fermat numbers:
F₅ = [641, 6700417]
F₆ = [274177, 67280421310721]
</pre>
| |||