It's a broad idea to construct a secure PoW, with all that's required to make it secure, but to try and make it applicable to areas like number theory. See PrimeCoin for a successful example.

Also your concerns are unfounded: See Namecoin and Primecoin. I'm thinking these two ideas could be combined.