It's a pretty narrow set of calculations that are very expensive but easy to verify. You have to be looking for needles in a haystack, and the haystack has to be gargantuan but not involve all that much data transfer.

So unless you feel that it's useful to find prime numbers, good luck.

The more "useful" you PoW algorithm is, the cheaper 51% attacks on your chain will be. To be maximally secure, a PoW algorithm should only generate useless data.