Does anyone know of a fast test to see if an arbitrary number is a semiprime -- deterministic or probabilistic? A test that returned "at least three prime factors" or "at most two prime factors" as output would suffice, if that's easier. In fact the algorithm could even output "unknown" as long as that only happened on a small fraction of inputs. Sieving up to the cube root takes exponential time. Factoring the number takes superpolynomial time. Is there something better?