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