> You would need to go over n primes and check them, but you might always finish too early.

I mean sure, but it's pretty simple to at least enumerate the primes < 100 and test those...