[cryptocoin]

Actually, no, it doesn't involve finding new primes. In fact it states clearly that it is not interested in finding large primes numbers (which is a requirement for finding new primes).

Primecoin's goal is to find chains of prime numbers, like the ones describe at https://en.wikipedia.org/wiki/Cunningham_chain

This is at least more useful than running a double sha on some input to produce some output that is hopefully less than a target t. But a altcoin that does something useful with its proof of work system is still not available.

[fragsworth]

Someone should make a coin whose proof of work involves solving difficult (but verifiable) problems that are in NP, that are frequently used in commerce.

This would provide a more direct incentive for researchers to make these algorithms faster, and would therefore provide a tangible benefit to society.