Factoring Integers Into Primes

Mathematical background
Problems

Mathematical Background

One way of factoring an integer n into primes is by trial division. This algorithm can be described as follows:

Given: a positive integer n

  Set d = 2   // the trial divisor
  While n > 1,
    If d divides n, 
    then
       write down the factor d,
       replace n by n/d
    else
       replace d by d + 1

Here is how it works for n = 60:

   1. d = 2 divides n = 60, so 2 is a factor.
      After replacement n = 30.
      Factors: 2

   2. d = 2 divides n = 30, so 2 is a factor.
      After replacement n = 15.
      Factors: 2 2
       
   3. d = 2 does not divide 2, so we
      set d = 3;
      Factors: 2 2

   4. d = 3 divides n = 15, so 3 is a factor
      After replacement, n = 5
      Factors: 2 2 3

   5. d = 3 does not divide n = 5, so 3 is not a factor.
      Set d = 4
      Factors: 2 2 3

   6. d = 4 does not divide n = 5, so we
      set d = 5
      Factors: 2 2 3

   7. d = 5 divides 5, so 5 is a factor.
      After replacement, n = 1.
      Factors: 2 2 3 5

   8.  n = 1, so we stop

Problems

Develop a C program which factors integers using this algorithm. Use the long data type so that you can factor large integers. Then factor the following: 12, 123, 1234, 12345, etc., up to 123456789. Factor also the integer 1234567898.
How does the running time of the program depend on the integer to be factored? In thinking about this problem, think about what kind of computation your program does most often, and how many times it does it.