> You might be able to come up with a more efficient algorithm.

Challenge accepted. Suppose we want to know the answer to 3 decimal places (so we'd match the headline). And suppose I allow my algorithm to be wrong one in a thousand times ("probably approximately correct").

Then sample some constant number C of random 64 bit integers. Run the following algorithm which separates each random sample into one of three classes: Y (has 32 but factors), N (does not have 32 bit factors), U (unknown).

Check if prime using probabilistic miller rabin. (Error prob goes to zero exponentially fast). If prime, return N. If it's not a prime, then run T steps of pollard rho to determine whether the number has 32 but factors; return Y,N, or U depending of the factors found up to step T.

The key observation is that T can be chosen to make the UNKNOWN class very small (with high probability), and so our estimate should rapidly converge to 17%Y, 83%N, ~0.001%U

For fixed error tolerance, this would run in roughly a constant number of iterations, independent of N.