But you could turn it around into finding factors of a very large number to check whether it is prime.
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...
A large number is proposed and everybody keeps dividing it by various primes until somebody gets lucky and finds a factor. It takes a lot of computational power to keep dividing but when you have found a factor
.