ifx>(2^40)thenprint("WARNING: Number is quite big. Due to Lua floating point limitations, draconic entities MAY be present and results may be blatantly wrong. If this runs for several seconds, it's probably frozen due to this.")end
-- by dividing n - 1 by 2 until this is no longer possible
locald=n-1
localr=0
whiletruedo
localddiv=d/2
ifddiv==floor(ddiv)then
r=r+1
d=ddiv
else
break
end
end
sleep()
for_,ainpairs(bases)do
localx=modexp(a,d,n)
ifx==1orx==n-1then
-- continue looping
else
localc=true
fori=2,rdo
x=(x*x)%n
ifx==n-1thenc=falsebreakend
end
ifcthen
returnfalse
end
end
end
primes[n]=true
returntrue
end
localfunctionis_power(n)
locali=2
whiletruedo
localx=pow(n,1/i)
ifx==floor(x)then
returni,x
elseifx<2thenreturnend
i=i+1
end
end
localfunctioninsertmany(xs,ys)
for_,yinpairs(ys)dotable.insert(xs,y)end
end
-- pollard's rho algorithm
-- it iterates again if it doesn't find a factor in one iteration, which causes infinite loops for actual primes
-- so a Miller-Rabin primality test is used to detect these (plus optimization for small primes); this will work for any number Lua can represent accurately, apparently
-- this also checks if something is an integer power of something else
-- You may argue that this is "stupid" and "pointless" and that "trial division would be faster anyway, the numbers are quite small" in which case bee you.