What is a fast algorithm to obtain the largest square-free divisor of a 64 bit unsigned integer. Can it be done without requiring full factorization?
radical(n) = prod_{p prime | n} p
I tackled this problem the following way. For larger numbers than 64 bit, probabalistic integer factorization algorithms faster than trial division by primes are probably going to be faster, but I used trial division by primes up to the cube root, so time complexity <= O(cbrt(n)). With some pre-computation for each of the first ~200k primes, the divisibility check can be performed using a multiplication which is quite a bit faster on most of todays hardware than using modulus or division. I expect this approach to be hard to beat in performance for 64 bit integers because of the simplicity of calculation of each divisibility check. My approach in pseudocode is described below. The functions isqrt() and icbrt() round down to the nearest integer.
function radical(n)
rad = 1
p = 2
isqrtn = isqrt(n)
while (n == (isqrtn*isqrtn))
n = isqrtn
isqrtn = isqrt(n)
icbrtn = icbrt(n)
while (p <= icbrtn)
if (p | n)
n /= p
rad *= p
while (n % p == 0) n /= p
if (n == 1) return rad
isqrtn = isqrt(n)
while (n == (isqrtn*isqrtn))
n = isqrtn
isqrtn = isqrt(n)
icbrtn = icbrt(n)
p = nextprime(p)
return rad*n
The main idea is that if you know that n is not square and does not have a prime divisor <= icbrt(n) then it must be a prime or the product of two distinct primes. You don’t need to know if n is prime or what its two prime factors are in this case to obtain the radical allowing it to exit after the cube root. My c coded function can be found here https://github.com/FastAsChuff/Fast-Square-Free-Integer-Functions.