Primes is a really good example because half of the proof is trivial (if I give you a factor, you can verify compositeness trivially), but verifying the other h

Primes is a really good example because half of the proof is trivial (if I give you a factor, you can verify compositeness trivially), but verifying the other half is a pretty big number theory rabbit hole.