Warning: Some math up ahead.
Originally Posted by Old Pedant
But even better: Why try moduloing the candidate with *every* number (even every odd number)?? Why not just try testing it against ALL THE PRIMES LESS THAN itself!
Even better: Only try all integers less than or equal to the square root of the number 
And now combining these two solutions, even better is to check all prime numbers less than or equal to the number .
As for algorithms in general: First off, the Sieve of Eratosthenes could be improved, but one could also use another optimized version known as the Sieve of Atkin which is better by a factor of 1/(log log n).
 If p was not prime, it could be factored into p = ab. Without loss of generality, assume a > sqrt(p). It would immediately follow that b < sqrt(p). Since finding only one factor suffices to disprove that p is a prime, it is enough to check all integers less than or equal to the square root of the number in question.
 The number of primes <= x is asymptotically equivalent to x/ln(x). The limit of that divided by sqrt(x) is -- as one can see with fairly basic maths -- infinite, which means that it is by far better to use sqrt(x). As an additional benefit the test is independent of all prime numbers smaller than the number in question.
 Again, if p was not prime, there would be a factorization p = ab. In  we have seen that we can assume a <= sqrt(p). Now, if a was not prime itself, it could be further factorized into a = xy. The same argument would show (without loss of generality) that x <= a <= sqrt(p).