Modern prime testing is quite far from brute force. Tests such as AKS[1], ECPP[2], and APR[3] can determine whether a number is prime in polynomial time (in the number of bits/digits), whereas a true brute force search would be exponential.
You're right, I misspoke I should have been more precise and said that out way of finding primes isn't based on a specific theorem or algorithm in that we still have to take a number and demonstrate its primeness.