See the discussion above. :) Prime number sequences are unlikely to be "useful" in the same sense as protein folding.

Another possibility.

Protein folding unfortunately isn't a good candidate, because verifying the work takes exactly as much effort as doing the work.

http://en.wikipedia.org/wiki/Proof-of-work_system