You might want to take a look at the Miller-Rabin primality test. In this test you use a series of "witness" values and perform some calculations. Each witness calculation gives a result of "composite" or "possibly prime". If you use k witnesses and they all give "possibly prime" results, the probability that the number is actually composite is 1/4^k.
The runtime is O(k log^3 n), which is a substantial improvement over your O(sqrt(n)) algorithm.