> There are alternatives to hashing proof-of-work
Not really. Peercoin's security comes from the developer of the system signing every block. It attempts to use a "Proof of Stake" system where ownership of coins controls mining, but the problem with PoS is, ironically, that there is nothing at stake.
In PoW when you attempt to mine you must expend energy and so you should only mine on a consensus which is likely to be the surviving one if you want your work to not be wasted. In PoS the same is not true, and an optimally rational PoS miner will attempt to concurrently mine all forks which he does not hate.
Originally the signed blocks in PPC were supposed to be a bootstrap mechanism until most of the mining was PoS based, but then some clever miner started mining many possible histories and finding ones where he magically got lucky and his coins were the selected stake for all the blocks.
Primecoin's work isn't scientifically useful— no one had bothered describing it as interesting before it got pulled out as a PoW, and it's far less clear that its not trapdoored (that someone knows how to mine it much faster) than the one way function based proof of work.
You can convert basically any stochastic search into a PoW, but not necessarily a good one (e.g. it might have trapdoors).
More deeply, if your mining work has independent value that that dilutes your incentive to mine on the one true best consensus, since you'll still gain that value even if you mine on a losing consensus.
And ultimately the energy is _not_ wasted: It provides security for the system which is shared by all it's users. In Bitcoin you don't mint coins (with enormous energy costs) or print notes, you don't need bank vaults, or armored cars. You don't need to incarcerate counterfitters, fly around agents, or suffer counterfeiting losses. All currencies have operating costs, if Bitcoin's costs are comparatively good is a complicated analysis which I don't think anyone's done.