I cringe every time someone thinks Bitcoin's collective hashing power is "wasted".
It just means you don't understand what it does - secures the network, and verifies transactions. There is no percentage "overhead" to capture, just like your automobile doesn't fix potholes in the street while at a stoplight, hashing isn't just shifting bits around for the hell of it.
Please, learn more before spewing out that old trope of "wasting" cycles.
It's definitely wasting energy if that energy could be used to both solve the necessary problems in securing the network AND something else useful, like what Primecoin does. Otherwise, you need to direct resources at securing the network, and the same (but independent) amount of resources at finding prime numbers. If we can merge the two workloads in the same amount of work without significant tradeoffs, it'd be stupid not to.
It's similar to how not doing BTC mining on a merged-mining-enabled pool is wasteful (or would be, if anyone used NMC). Mining can be a lot more than it is -- we just haven't been creative enough. Maybe one day a SETI-like coin will come out, where you can solve the problems they deem important while securing the SETIcoin network at the same time with no significant increase in work to do both at the same time.
This isn't a knock against bitcoin then. According to your definition, EVERYTHING humans do is wasteful.
Probably. Nothing's perfect. That's why we generally strive to become more efficient. Cryptocurrency software, protocols, and what have you are full of waste, and devs are improving it every day -- all through different means. It's pretty much the first rule of industry everywhere; nothing is ever finished. It can always be improved.
Primecoin and other solutions looking at the problem with a similar premise are all basically looking at ways to recycle computational power already used, so it can be more efficient. Think of it like feed corn. You could try to eat the corn and say "good enough," or you could use the corn to feed to cows - and at that point, you could say "good enough," or you could feed the corn to cows, and then use the manure as fertilizer for feed corn growth - and at that point, you could say "good enough," or you could make a bomb.
(this is a... shit... example, though, because with something like Primecoin, the devs did all the work up-front to make future work more efficient - you don't have to keep collecting manure... .... ... yeah, really bad analogy)