Elementary number theory would have us try to divide a number N by each prime number that is smaller than its square root. In practice, generating the set of all small primes is impractical. The usual approach is trial division by all positive integers, no matter if they are composite or not.
A naive approach is to try to divide by each integer from two up the the number N itself. (Any number N is divisible by one and itself). If the number is prime. this would result in N - 1 divisions and the process would start to take quite a lot of time when the number was six or more digits long. A somewhat improved approach is based on the realization that if a number is not divisible by two, then it is not divisible by any even integer. This leads to an algorithm in which the number is tested for division by two separately. If it is not even then start with three and add two to the trial divisors. This process will cut the number of test divisions approximately in half.
The key to a real speedup in the process is to realize that if a number N is divisible by some factor K, then it is also divisible by N/K. If K is the smaller of the two, then K <= SQRT(N) <= N/K. So - you can quit the process if no integer divisors exist in the range 2,...,SQRT(N) and the number of divisions is proportional to the square root of N.
On my current machine (a 4.50 GHz P4), the factorization of the fourteen digit number 20,865,628,187,881 (which is 4567891 * 4567891) takes about 1.5 seconds. (If you cut and paste this number, be sure to take out the commas.) The current Advanced Encryption Standard uses keys of 128, 192, or 256 bit primes. A 128 bit prime is about 39 decimal digits long. If a number is two decimal digits longer, its square root is approximately 10 times larger and so a 128 bit prime has a square root that is about 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 * 10 times larger that of a 14 digit number (one ten for each two digit difference in the lengths - give or take). Even if this program was capable of handling numbers that large, it would take on the order of 1.5 * 1012 seconds to factor, or about 47,500 years. (Of course parallel machines with vector processors could do the job much faster)