Euclid-Mullin sequence: Difference between revisions
→{{header|Lua}}: Added alternative using Pollard's rho algorithm, as in the Ruby sample
(→{{header|Ruby}}: Add Ruby) |
(→{{header|Lua}}: Added alternative using Pollard's rho algorithm, as in the Ruby sample) |
||
Line 626:
end
end
</syntaxhighlight>
{{out}}
<pre>
2 3 7 43 13 53 5 6221671
</pre>
Alternative using Pollard's Rho algorithm. Uses the iterative gcd function from the [[Greatest common divisor]] task.<br>
{{Trans|Ruby|for the Pollard's Rho algorithm}}.
Note that, as discussed on the Talk page, Pollard's Rho algorithm won't necessarily find the lowest factor, however it does for the first 16 elements.<br>
As with the other Lua sample, only 8 elements are found due to the size of some of the subsequent ones.
<syntaxhighlight lang="lua">
function gcd(a,b)
while b~=0 do
a,b=b,a%b
end
return math.abs(a)
end
function pollard_rho(n)
local x, y, d = 2, 2, 1
local g = function(x) return (x*x+1) % n end
while d == 1 do
x = g(x)
y = g(g(y))
d = gcd(math.abs(x-y),n)
end
if d == n then return d end
return math.min(d, math.floor( n/d ) )
end
local ar, product = {2}, 2
repeat
ar[ #ar + 1 ] = pollard_rho( product + 1 )
product = product * ar[ #ar ]
until #ar >= 8
print( table.concat(ar, " ") )
</syntaxhighlight>
{{out}}
| |||