It needs to be valueless, not useless. Finding primes actually seems like something that might be both useful and low-value.
Anything with a use has value to a person benefiting from that use. The trick is to make it such that out-of-band payments to specific miners are not likely to occur.
That's not to say that it's absolutely, 100% a priori impossible to have a "useful but no-value" proof of work. Only theorized example I know of is time-lock decryption: you have a deterministic process for generating public keys, and the proof of work solution is the recovered private key. However this invalidates other assumptions that are required of a secure proof of work, at least with all existing public key crypto systems.
Vitalik says cryptocurrency developers should "reach out to LessWrong more", in order to not be ignorant of advanced computer science and game theory topics.
https://blog.ethereum.org/2014/12/31/silos/
I think Vitalik raises several major important points, namely:
* Bitcoin's $600 million wasted on electricity yearly in order to secure the network is a huge problem. Various Proof of Stake algorithms are attempting to improve upon this. The ideal solution would be one which combines the low cost of the Proof of Stake algorithm, with the high security or Proof of Work. I not enough of an expert to be able to say which solution is best, but both the Ripple consensus algorithm and the Bitshares Delegated Proof of State algorithm look promising. I am interested to see what algorithm Vitalik will choose for Ethereum.
* ASIC miners are a problem due to the resulting centralization. They have also lead to increased centralization in Bitcoin, as the network is now increasingly controlled by a few large mining pools.
* Blockchain technologies have a great potential to change the world, and solve governmental and organizational problems that society is facing. Beyond simply revolutionizing money, blockchain technologies could also be used in the future to support prediction markets, voting/consensus building, exchanges, etc.