# Factoring Integers Into Primes

## 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

1. 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.
2. 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.

Back to syllabus
Back to Department of Mathematics, University of Utah