Factoring Integers Into Primes
-
Mathematical background
-
Problems
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
-
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.
Back to syllabus
Back to Department of Mathematics, University of Utah
Last modified: Feb 21, 1995
Copyright © 1995 Department of Mathematics, University of
Utah