Computing Factors Algorithmically

Thursday, August 21, 2008

Introduction

Do you remember, way back in grade-school, when you were taught how to find the prime factors of a number? It was the biggest pain… especially since you knew that your teacher already knew the factors of that number, and that any work you did was not for anyone’s benefit. Let us face the cold, hard facts: factoring 27 into 1, 3, 3, 3 did not put food on anyone’s table, did not help a soldier compute the trajectory of a mortar rocket, and it certainly did not make your day any better (if, on the other hand, it did brighten your day, please email me; I am also a counselor. ­čśŤ )

Perhaps now, so many years later, you have been demanded to program an algorithm to factor a number. I can hear your groans; once again, accomplishing this will not save the world. However, writing such an algorithm is not beyond the astute programmer. Actually, it can be quite fun. Let us walk step-by-step through this such daunting task.

(SIDE NOTE: All code on this page is in pseudo-code. Therefore, most schools will allow you to read this article without infringing on cheating policies.)

A Brute-Force Factoring Method

First, let us look at the most basic of factoring methods. We will start with a number–say, 6:

let rawNumber = 6

We all know (from grade-school) that the factors of 6 are 1, 2, 3 (1 x 6 = 6, 2 x 3 = 6, right?). We also know that 2 and 3 are the only numbers that will divide equally into 6. So, all we have to do for the simple method is to start at 1 and see if it divides equally into 6 (it does).

let 'currentFactor' = 1
let 'test' = 'rawNumber' / 'currentFactor'
is 'test' an integer (with no decimal part to it)? -- Yes

So, we store┬á‘currentFactor’ in the list of factors we have found:

foundFactors.add('currentFactor')

Then, we test the numbers 2 and 3. They give us the same result, so we store them like before. Number 4, however, does not evenly divide into 6:

let 'currentFactor' = 4
let 'test' = 'rawNumber' / 'currentFactor'
is 'test' an integer (with no decimal part to it)? -- No

So, we do not add 4 to the list of factors found. Neither do we add 5 to that list. Finally, we arrive at 6, which is the number tested so we do not have to bother dividing it. The complete pseudocode listing:

let rawNumber = 6
let 'currentFactor' = 1
let 'test' = 'rawNumber' / 'currentFactor'
is 'test' an integer (with no decimal part to it)? -- Yes
foundFactors.add('currentFactor')
let 'currentFactor' = 2
let 'test' = 'rawNumber' / 'currentFactor'
is 'test' an integer (with no decimal part to it)? -- Yes
foundFactors.add('currentFactor')
let 'currentFactor' = 3
let 'test' = 'rawNumber' / 'currentFactor'
is 'test' an integer (with no decimal part to it)? -- Yes
foundFactors.add('currentFactor')
let 'currentFactor' = 4
let 'test' = 'rawNumber' / 'currentFactor'
is 'test' an integer (with no decimal part to it)? -- No
let 'currentFactor' = 5
let 'test' = 'rawNumber' / 'currentFactor'
is 'test' an integer (with no decimal part to it)? -- No

This listing works… but only for the number 6. It is not scalable to any other number, not even 5 or 7. What we need is a loop. Explaining programmatic loops is beyond (or, rather, below) the scope of this article, but you may explore the MSDN reference page for C#’s for loops. Inserting a loop is easy, and it makes managing even this small code-base much easier:

let 'rawNumber' = 6
for 'currentFactor' = 1 to 'rawNumber' - 1
   let 'test' = 'rawNumber' / 'currentFactor'
   is 'test' an integer (with no decimal part to it)? --
      if so, foundFactors.add('currentFactor')
continue for loop

Now, we can test any number by simply changing the first line, setting ‘rawNumber’ to, say, 7, or 3, or 188! This basic┬ámethod works perfectly. However, any professor worth his salt will fail you if you turn in such a method. Why? It takes so very long! In factoring, we humans have certain intuitions that computers do not have. For instance, we know automatically that 5 will never, ever divide evenly into 6. I know what you may be thinking: that does not take much time for my blazing-fast gaming machine to compute! What if the computer were trying to factor 144? 1444? 14444444444444? What if it had to factor a million such numbers? Do you want to wait while it loops through values that are so clearly impossible that even a blind mole could figure them out? I didn’t think so. So, clear the stands (but not your memory of our previous algorithm… you’ll need that) and usher in…

The Factoring Algorithm, Optimization Level 1

…coming soon…

Leave a Reply