Anonymous user
Fermat numbers: Difference between revisions
→factoring via Pollard's rho algorithm: optimized the RHO function.
m (→factoring by trial division: changed a comment.) |
(→factoring via Pollard's rho algorithm: optimized the RHO function.) |
||
Line 1,701:
numeric digits 200 /*ensure enough decimal digits, for n=9*/
do j=0 to n; f= 2** (2**j) + 1
say right('F'j, length(n) + 1)': '
end /*j*/
say
do k=5 to n; f= 2** (2**k) + 1;
say center(' F'k": " f' ', 79, "═")
a= rho(f)
b= f % a
if a==b then say f ' is prime.'
else say 'factors: ' commas(a) " " commas(b)
end /*k*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg _; do ?=length(_)-3 to 1 by -3; _=insert(',', _, ?); end; return _
/*──────────────────────────────────────────────────────────────────────────────────────*/
rho: procedure; parse arg n; y= 2; d= 1 /*initialize X, Y, and D variables.*/
do x=2 until
do while d==1
x= (x*x + 1) // n
v= (y*y + 1) // n
Line 1,730:
d= xy /*assign variable D with a new XY */
end /*while*/
▲ end /*x*/</lang>
{{out|output|text= when using the default input:}}
<pre>
|