Well, no, primes aren't very useful, though this might have lead to a bit of an arms race in probabilistic prime-finding algorithms - which would be good, I suppose.
I wonder if you could make a proof-of-work algorithm based on, say, protein folding?