There are many fast algorithms (deterministic and probabilistic) for detecting primality. Are there any fast algorithms (probabilistic ones allowed) known for detecting whether a number is the product of at most two primes?
In this context, can anybody think of a property fulfilled by all or most products of two primes, but by few other numbers? (You can't explicitly use divisor sums or the Moebius function, obviously, as then the game becomes (a) trivial (b) of doubtful computational utility.)