generally that is true, but consider that once a prime is found and verified then there is little dispute that it is indeed a prime.  The idea wouldn't work like regular Bitcoin, instead it must appeal to some kind of authority that says it prime.  Of course the P2P fanatics will claim that's 'centralized' but you couldn't pass of a non-prime as a prime, right?  If someone found a composite to the pseudoprime then they lose their block.  It's a just a fanciful thought at this point   Just want to put all these computers to work on something useful.  Seems primes are discovered in batches so I dont expect new primes to be discovered on a regular basis.

It would be something like the nobel prize.  If you discover a new prime you get a block reward.  Imagine we harnessed the power of all these mining rigs and the best mathematicians to solve some of the mysteries of mathematics?