Q:

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).

