Couldn't you just lie about this? Imagine "15" is such a huge number: I just claim that the only factors I could find for 15 are 1 and 15, thus making it prime. This still requires you to try to find other factors to debunk my claim...

I think "useful" would maybe work with predictions (e.g. the stock scenario) as it would also leave open the actual implementation up to the users. Still you would need to predict something that can be observed from everyone on the whole earth and that on the other hand is not under the control of an entity that might restrict access or manipulate the observation itself.

Other "useful" examples would be for instance SAT solving a huge set of clauses (that you could generate randomly) - to make it really hard though you would need to generate probably quite large sets after some time and then they become less and less useful again. Also you could utilize existing solutions to make tiny alterations and submit a new solution so you would need to guarantee that no other set of clauses was being used to even generate your intitial set in the first place.