The problem is that mining requires a work that is hard to find but easy to verify.
Prime numbers don't work because finding one is as difficult as verifying it's prime
I've already discussed this idea on another thread
https://bitcointalk.org/index.php?topic=233750.msg2509289#msg2509289There are ways of reconstructing the problem so that it satisfies the pow requirements such as changing the problem to finding a factor of a large number.
you basically restated what I suggest at the beginning of this thread, but two days later.