Rosetta Code

Euclid-Mullin sequence: Difference between revisions

Page Discussion

Euclid-Mullin sequence (view source)

Revision as of 09:04, 23 July 2023

440 bytes removed ,  10 months ago
→‎Wren-cli: Aligned code with GMP version and now using library version of Pollard's Rho.
(→‎Embedded: Re-jigged to find the first 27 numbers in a reasonable time.)
(→‎Wren-cli: Aligned code with GMP version and now using library version of Pollard's Rho.)
Line 795:
var two = BigInt.two
var ten = BigInt.ten
var max k100 = BigInt.new(100000)
 
var pollardRhosmallestPrimeFactorWheel = Fn.new { |n, cmax|
var g = Fn.new { |x, y| (x*x + c) % n }
var x = two
var y = two
var z = one
var d = max + 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 != one) break
z = one
count = 0
}
}
if (d == n) return zero
return d
}
 
var smallestPrimeFactorWheel = Fn.new { |n|
if (n.isProbablePrime(5)) return n
if (n % 2 == zero) return BigInt.two
Line 838 ⟶ 814:
 
var smallestPrimeFactor = Fn.new { |n|
var s = smallestPrimeFactorWheel.call(n, k100)
if (s) return s
var c = one
swhile =(true) n{
▲ var d = BigInt.gcdpollardRho(zn, n2, c)
while (n > max) {
var d = pollardRho.call(n, c)
if (d == 0) {
if (c == ten) Fiber.abort("Pollard Rho doesn't appear to be working.")
c = c + one
} else {
// can't be sure PR will findget the smallest prime factor firstof 'd'
svar factor = BigIntsmallestPrimeFactorWheel.mincall(sd, d)
n// =check nwhether n/ d has a smaller prime factor
ifs (n.isProbablePrime(2))= return BigIntsmallestPrimeFactorWheel.mincall(sn/d, nfactor)
return s ? BigInt.min(s, factor) : factor
}
}
return s
}
 
Line 867 ⟶ 842:
prod = prod * t
count = count + 1
} ></syntaxhighlight>
 
{{out}}
Line 890 ⟶ 865:
</pre>
<br>
 
===Embedded===
{{libheader|Wren-gmp}}
PureFox
9,485

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/346772"