Intrinsically useful proof-of-work using Mersenne or Fermat numbers factorization. Could it be possible?
How would solving these problems secure the network? Miners are rewarded for the proof of work they do because the specific proof of work they do -- hashing block headers -- in fact secures the system. Solving other problems doesn't secure the currency. If you want to pay people for doing work, you certainly can. But don't at all confuse it with the proof-of-work that crypto-currencies use to solve the double spend problem -- that must be the actual proof-of-work that actually solves the double spend problem.

The point is that the block hashes are tied to a specific block and to specific transactions in that block. The proof of work cannot be severed from the block header and the transactions. Thus the proof of work secures that block header and those transaction. Factorization of Mersenne numbers isn't tied to a specific block or set of transactions, so it does not secure the block chain.