A Faster Way to Compute Factors

A conceptually simple and straight-forward way to calculate the factors of a given number n, might look like the below code:

# ruby
def factors(n)
(1..n).select { |int| n % int == 0 }
end
// javascript
function factors(n) {
return Array(n).fill().map((_, idx) => idx + 1)
.filter(int => n % int === 0);
}

These code samples do the job. They iterate through an inclusive list of numbers 1 through n, selecting only those numbers by which n can be divided evenly. The returned result is an array of n's factors, as expected. While this approach works, it is what we call a “brute force” approach and it is very slow. The speed of the code may not be of much consequence when we are computing the factors of a relatively small number. However, if the input is a very large number the inefficiency of this algorithm becomes apparent. We can be more clever than this.

A Faster Approach

Rather than iterating through every number from 1 to n, we can instead stop after reaching the square root of n. Or, more precisely, the floor of the square root of n (in the case of a square root that is not a whole number). For example, the square root of 48 is 6.92820323028. When computing the factors of 48, we should iterate from 1 through 6.

When using this approach, we may add up to two numbers to our list of factors on each iteration. Conceptually, it helps to think of our factors as pairs. Imagine a 2D array that holds all of the factors of 24: [[1, 24], [2, 12], [3, 8], [4, 6]] , why not add both elements of a pair at the same time? (note: the code below produces a flat array of factors). As we iterate from 1 to the square root of n, when we find a whole divisor of n ( let that be i ) we will add i to the list of factors along with the number by which we must multiply i in order to return the product n.

There is one exception. When finding the factors of a square number, you likely only want to include the square root once. We account for that on line 8 of the below code.

# ruby
def factors(n)
factors = []
limit = Math.sqrt(n).floor
(1..limit).each do |i|
if n % i == 0
factors.push(i)
factors.push(n / i) if (n / i) != i
end
end

factors
end

Here is the same approach written in JavaScript:

// javascript
function factors(n) {
const factors = [];
const limit = Math.floor(Math.sqrt(n));
for (let i = 1; i <= limit; i++) {
if (n % i == 0) {
factors.push(i);
if (n / i !== i) { factors.push(n / i) }
}
}
return factors;
}

If you test this code out with some smaller numerical arguments, you aren’t likely to notice a difference in the code’s speed. You may look at the increased number of lines in the more efficient code and think “is it really necessary?”. Try to run these code samples instead with a much larger input — factors(108800324) — and you will notice a major difference. In fact, the original JavaScript implementation of factors may raise an error — JavaScript heap out of memory.

Benchmarking

You can examine the difference in the speed of our two ruby methods, factors, using the Benchmark module. It’s pretty simple! Below, I’ve renamed our two ruby methods to differentiate them, and used the Benchmark module to analyze their speed.

require 'benchmark'def slow_factors(n)
(1..n).select { |int| n % int == 0 }
end
def faster_factors(n)
factors = []
limit = Math.sqrt(n).floor
(1..limit).each do |i|
if n % i == 0
factors.push(i)
factors.push(n / i) if (n / i) != i
end
end
factors
end
Benchmark.bm do |bm|
bm.report { slow_factors(108_800_324) }
bm.report { faster_factors(108_800_324) }
end

Here is the data reported:

user     system      total        real8.250000   0.010000   8.260000 (  8.265131)0.000000   0.000000   0.000000 (  0.000724)

What a difference! This example uses a very large input, but you will still see a difference using a small input:

Benchmark.bm do |bm|
bm.report { slow_factors(6024) }
bm.report { faster_factors(6024) }
end
# data:
user system total real
0.000000 0.000000 0.000000 ( 0.000467)
0.000000 0.000000 0.000000 ( 0.000018)

In JavaScript, the console.time and console.timeEnd methods are fun. Using the argument 108800324 with our slower factor function ended up raising an error, so we’ll have to compare our code with something a little smaller.

I renamed the two JavaScript factor functions to differentiate them, and ran them with the code below:

console.time("slow factors");
slowFactors(1800324);
console.timeEnd("slow factors");
console.time("faster factors");
fasterFactors(1800324);
console.timeEnd("faster factors");

The output is:

slow factors: 1455.518ms
faster factors: 0.143ms

You can see the significant difference in speed here, even with a much smaller numerical argument.

As a beginner programmer, or when first conceptualizing how to approach a problem you haven’t seen before, I recommend first outlining the simplest approach possible — even if it is “brute force”. Don’t try to be too clever straight away. Pay close attention to the problem requirements and use a methodical, step-by-step plan to solve some simpler test cases. Once you have confirmed your understanding of the problem, explore in more detail how you might optimize your code to perform the work more efficiently.

The example of producing a list of factors for a number n is pretty simple, but I have found this pattern to be beneficial when working on problems of all levels of difficulty. I hope this simple walkthrough has been helpful to those trying to establish a similar pattern in their own work!