How hard is it to count the number of factors of an integer?
This isn't my answer, but Terrence Tao gave a beautiful answer to this question on MathOverflow.

Here are the first few lines of his answer. To read the complete answer, follow the link.


  There is a folklore observation that if one was able to quickly count the number of prime factors of an integer n, then one would likely be able to quickly factor n completely. So the counting-prime-factors problem is believed to have comparable difficulty to factoring itself.


(I wasn't sure whether this should be an answer or a comment. But it is really an answer, although it isn't written by me. I've made the answer Community Wiki so that it may be upvoted or accepted without unnecessarily giving me reputation.)