|
===Wren-cli===
ThisThe usesbuilt-in routines use a combination of the Pollard Rho algorithm and wheel based factorization to try and factorize the large numbers involved here in a reasonable time.
Reaches HP20 in about 0.52 seconds but HP65 took just under 40 minutes!
<lang ecmascript>import "/math" for Int
import "/big" for BigInt
import "/sort" for Sort
// simple wheel based prime factors routine for BigInt
var primeFactorsWheel = Fn.new { |n|
var inc = [4, 2, 4, 2, 4, 6, 2, 6]
var factors = []
while (n%2 == 0) {
factors.add(BigInt.two)
n = n / 2
}
while (n%3 == 0) {
factors.add(BigInt.three)
n = n / 3
}
while (n%5 == 0) {
factors.add(BigInt.five)
n = n / 5
}
var k = BigInt.new(7)
var i = 0
while (k * k <= n) {
if (n%k == 0) {
factors.add(k)
n = n / k
} else {
k = k + inc[i]
i = (i + 1) % 8
}
}
if (n > 1) factors.add(n)
return factors
}
var pollardRho = Fn.new { |n|
var g = Fn.new { |x, y| (x*x + BigInt.one) % n }
var x = BigInt.two
var y = BigInt.two
var z = BigInt.one
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|
var factors = []
while (n > 1) {
if (n > BigInt.maxSmall/100) {
var d = pollardRho.call(n)
if (d != 0) {
factors.addAll(primeFactorsWheel.call(d))
n = n / d
if (n.isProbablePrime(2)) {
factors.add(n)
break
}
} else {
factors.addAll(primeFactorsWheel.call(n))
break
}
} else {
factors.addAll(primeFactorsWheel.call(n))
break
}
}
Sort.insertion(factors)
return factors
}
var list = (2..20).toList
list.add(65)
var h = [j]
while (true) {
var k = primeFactorsBigInt.callprimeFactors(j).reduce("") { |acc, f| acc + f.toString }
j = BigInt.new(k)
h.add(j)
</pre>
<br>
===Embedded===
{{libheader|Wren-gmp}}
|