I wrote some code determining whether a number n is square free, and decided I want to make it as fast as I can. A number that isn't square free is either a square or the product of at least three primes, so we only need to check whether n is divisible by p for $p ≤ n^{1/3}$, which can be done in $O(n^{1/3})$ or in $O(n^{1/3} / \ln n)$ if we have a table of primes, plus one check whether n is square.
Then I thought I could find large prime factors using Pollard-rho. Pollard rho finds a prime factor p in $O(\sqrt p)$. It will find the smallest prime factor of a number with three prime factors in $O(n^{1/6})$. The problem: What if n is square free?
We can run say $5 \cdot n^{1/6}$ rounds of Pollard-rho and if no factor is found, then we suspect or suspect strongly that n doesn't have three prime factors. We can test quickly that n is not a prime and not the square of some number. At this point, to prove that n is square free we have to prove that it is not semi-prime.
One idea is a probabilistic test: We run Pollard-rho for $c \cdot n^{1/6}$ rounds, and if c is large enough then we can argue that n is a probabilistic semiprime, otherwise the smallest of three or more factors would have been found. Has anyone checked for which c we can use that argument?
The other question is obviously whether there is any other method to test whether n can be proven to be semiprime if it is semiprime. If it isn't semiprime then either Miller-Rabin will show very quickly that it is very probable prime, and Pollard-rho will be very likely to find one of three or more factors.
Note that a very similar question (is n a semiprime) has been closed by pointing to answers trying to find factors. Which is obviously not answering either question at all.