ColdFusion UDF: Calculate A Number's Divisors
Posted by
Brad Wood
Aug 15, 2009 06:24:00 UTC
Here's another UDF I was tinkering with last week. I wanted to be able to count all of the numbers that divided evenly into a given integer. I couldn't find a ColdFusion implementation, so after getting some advice from Stack Overflow I created my own.The first version of my function used a process known as Prime Factorization. This means you represent the number as factors of its primes. For example, 24 can be shown as:
2 x 2 x 2 x 3 = 24
Similarly, 50 can be represented as:
2 x 5 x 5 = 50
Another way to put those is like so:
23 x 31 = 24
and
21 x 30 x 52 = 50 Once you have represented a number as a factor of its primes, the shortcut is to add 1 to each of the exponents and take their product. So, if 24 = 23 x 31, take the 3, and the 1, add one to them, and mulitply. (3+1) x (1+1) = 4 x 2 = 8 There are 8 integers that divide evenly into 24. Let's try it with 50. 50 = 21 x 30 x 52
(1+1) x (0+1) x (2+1) = 2 x 1 x 3 = 6. There are 6 integers that divide evenly into 50. Ok, let's look at the code I wrote to accomplish this. First, I needed all the prime numbers up to the number in question. I wrote a UDF called getPrimes() which returns an array of prime numbers up to your specified threshold. Coincidentally, it was the subject of my previous blog post. The function takes the array of primes, and starts dividing them into the number (and its subsequent remainder) as long as it will go in evenly. Then it moves on to the next prime number, keeping track of how many times they each went in with the exponents array. (each index of the exponents array corresponds with the similarly indexed position in the primes array.)
and
21 x 30 x 52 = 50 Once you have represented a number as a factor of its primes, the shortcut is to add 1 to each of the exponents and take their product. So, if 24 = 23 x 31, take the 3, and the 1, add one to them, and mulitply. (3+1) x (1+1) = 4 x 2 = 8 There are 8 integers that divide evenly into 24. Let's try it with 50. 50 = 21 x 30 x 52
(1+1) x (0+1) x (2+1) = 2 x 1 x 3 = 6. There are 6 integers that divide evenly into 50. Ok, let's look at the code I wrote to accomplish this. First, I needed all the prime numbers up to the number in question. I wrote a UDF called getPrimes() which returns an array of prime numbers up to your specified threshold. Coincidentally, it was the subject of my previous blog post. The function takes the array of primes, and starts dividing them into the number (and its subsequent remainder) as long as it will go in evenly. Then it moves on to the next prime number, keeping track of how many times they each went in with the exponents array. (each index of the exponents array corresponds with the similarly indexed position in the primes array.)
[code]function getDivisors(num)
{
var primes = getPrimes(num);
var exponents = [0];
var p = 1;
var r = 0;
while(num > 1 && p <= arrayLen(primes))
{
r = num/primes[p];
if(r == int(r)) {
exponents[p]++;
num = r;}
else {
p++;
exponents[p] = 0;}
}
p = 0;
r = 1;
while (++p <= arrayLen(exponents))
r *= (exponents[p]+1);
return r;
}
[/code]
This method worked pretty well, but the performance was mostly limited by the getPrimes() part which was taking about 30 seconds to return all the prime numbers up to 10 million.
So, in the spirit of improvement, I tried a second version, which was a bit more brute-ish, but performed much faster. This second version, simply tried to divide every number between 1 and the square root of our dividend and kept track of each one that divided in evenly. The reason you stop at the square root, is because you will have reached every divisor by then.
[code]function getDivisors2(num) {
var sqrt = sqr(num);
var divisors = [];
var i = 0;
var r = 0;
while(++i <= sqrt) {
r = num/i;
if (r == int(r)) {
divisors[arrayLen(divisors)+1] = i;
if (i != r) divisors[arrayLen(divisors)+1] = r;}}
return arrayLen(divisors);}
[/code]
This method proved to be simpler, and much faster. In fact, it can figure out how many divisors are in 10 TRILLION in about 1.3 seconds. (196 in case you were wondering) I also like the second version better because it can easily be changed to simply return the array of divisors instead of the count.