As you find factors you can divide them out. If there are no factors smaller than $\sqrt n$ the number is prime, which is much smaller (for large $n$) than $n/2$. Factoring is believed to be hard-this is the basis of the security of RSA encryption. It is easy to prove a number composite and relatively easy to prove a number prime, but if you have a large number that is the product of two large primes it is believed to be impractical to find the factors. We don't have a proof that it is hard, but lots of people have tried and failed. If somebody did find a solution to factoring it is not clear they would publicize it because they could use it to decrypt things we believe to be secure.