> They aren’t hard to find, though, it’s (as far as we know) hard to recognize integers as being primes.

Depends on what you mean by 'hard'. It's easy in the sense that we have algorithms to decide whether a number is prime or composite that take time polynomial in the space it takes to write down your number (ie polynomial in log n).