Why is it faster to first check if a number is a pseudoprime than to divide by all integers up to, but not including, that number? The Oxford Concise Dictionary of Mathematics defines a pseudoprime as any number $n$ that satisfies the condition $a^n = a \pmod n$ "for all integers $a$". To find a pseudoprime, we have to go about iterating through each integer less than $n$, at least until we get to the point where we can be sure none of the numbers that follow are factors of $n$. Then, if we wish to be sure any number we have is a prime, we still have to divide that number by each of the aforementioned integers.
Wouldn't it be easier to test each n the "grade-school" way?
Edit: I mean, if we do all this stuff on a computer, there can't be that much of a difference between the two tests. 
 A: Let's say we had a number $n$ of size roughly $10^{100}$.  To test for primality by trial division, we would  have to divide by all the primes up to about $10^{50}$ (if the number is in fact prime). According to the Prime Number Theorem there are about $\frac{10^{50}}{\ln\left(10^{50}\right)}\approx 8.7\times10^{47}$ primes to try dividing by.
On the other hand a pseudoprime test with the base $b$ requires calculating the least nonnegative residue of $b^{n-1}\pmod{n}$.  Using a successive squaring algorithm, this only takes about $335$ squarings (for our number in the range of $10^{100}$), multiplications, and modular reduction steps (each of these steps takes a few--about $5$--multiplications and divisions).  So that's about $1700$ multiplication and divisions, compared to $10^{47}$ multiplications and divisions for verifying a prime by trial division.
For a computer, verification of a prime in the range of $10^{100}$,  takes forever (well not quite literally, but longer than the age of the universe); whereas the pseudoprime test can be done in a matter of seconds (maybe less than a second).
A: Let me point out the falsity of the last statement in the question, claiming that "if we wish to be sure any number we have is a prime, we still have to divide that number by each of the aforementioned integers."
Trial division is not the only way to verify a number is prime, and it is not the most efficient way for large integers.  Trial division for prime $n$ requires integer divisions up to $\lfloor \sqrt n \rfloor$.  From a complexity perspective this is an exponential number of operations in terms of the size of input (the bit size of $n$, or $\log_2 n$).
It is known that there exist polynomial-time deterministic algorithms to check primality. See Primes is in P: A Breakthough for "Everyman".
For all practical purposes the problem of primality testing can be addressed by a slight variation of the pseudoprime test mentioned in the Question, namely the strong pseudoprime test for a sufficient number of relatively prime bases.
This is easily implemented.  If $n$ fails a strong pseudoprime test for any base, it is certainly composite (and such a base is called a "witness" for the compositeness of $n$).  
If a probabilistic test (of arbitrary accuracy) is satisfactory, then because a composite number $n$ fails the strong pseudoprime test for at least three-quarters of the bases coprime to $n$ between $1$ and $n$, the chance a composite $n$ would pass $k$ of these tests for bases chosen randomly is (conservatively) less than $2^{-2k}$.  Thus we can control how small we want to make the chance that a "probable prime" is really composite.
This can also be considered a deterministic check, whose sufficiency depends on an Extended Riemann Hypothesis (ERH), which implies the smallest base for which a composite $n$ fails the strong pseudoprime test is at most $2 (\ln n)^2$.  It follows that if ERH is true, then primality can be checked deterministically by no more than that many strong pseudoprime tests, which means the entire test has complexity $O((\ln n)^3)$.  For more details see the Miller-Rabin primality test.

Added:  The description of trial division implied in the title of the Question is also overly pessimistic.  If $n$ is a composite natural number, all but one prime factor will be at most $\sqrt n$, so we will try to divide (in the worst case) by whole numbers up to that limit (not "by all integers" less than $n$).
Indeed we don't need to try to divide by every integer up to $\sqrt n$ because if $k$ doesn't divide $n$, neither will any larger multiples of $k$.  In particular, once it is known that $2$ does not divide $n$, we need not check for divisibility by any larger even integers.  Carried to the extreme this means we only need to try dividing $n$ by a set of "trial divisors" $k$ which contains all the primes that do not exceed $\sqrt n$.
