# Find all factors of an integer

My script finds all factors of an integer. First it finds all prime integers using trial division then it uses the prime factors to find all other factors of the integer.

I would like to know how I can improve and simplify it. I think the code that prevents duplicate factors such as 4 x 5 and 5 x 4 probably could be improved but this is the simplest way I could think of.

Also, I am hoping that this is accurate and works for integers up to 99,999 but I have no idea how I could even test for that?

My script on JS Bin: http://jsbin.com/arucuy/1/edit

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<title>All Factors 1</title>
<script>
// Find all factors
var n = 20;

// Save the inputted number above for later use
var n2 = n;

// Store prime factors in array
var primeFactorsArray = new Array();

// Store all factors in array
var allFactorsArray = new Array();

// Prime numbers list - saves time - currently goes up to 1,000 - not sure how high I should go if I plan on finding prime factors of integers up to 99,999?
var primeNumbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997];

// Trial division algorithm to find all prime factors of inputted number
for (var i = 0, p = primeNumbers[i]; i < primeNumbers.length && p * p <= n; i++, p = primeNumbers[i]) {

while (n % p == 0) {
primeFactorsArray.push(p);

n /= p;
}
}

if (n > 1) {
primeFactorsArray.push(n);
}

/////////////////////////////////////////////////////////////////////////////
// Use the prime factors above to find all the factors of the inputted number
for (var i = 0, p = primeFactorsArray[i]; i < primeFactorsArray.length; i++, p = primeFactorsArray[i]) {

// Check that the prime number isn't a duplicate
// Example: 20 = 2 x 2 x 5 --- We only want to try 2 once
if (primeFactorsArray[i] !== primeFactorsArray[i-1]) {

while (n2 % p == 0) {

otherFactor = n2 / p;

// Prevent duplicate factors
// Example: 20 --- 4 x 5 and 5 x 4 are duplicate factors of 20
for (var t = 0; t < primeFactorsArray.length; t++) {

if (otherFactor == primeFactorsArray[t]) { // if otherFactor is a prime number don't add it
} else {
}
}

allFactorsArray.push(p + " x " + otherFactor);
}

p *= p;
}
}

}

// Display stuff
document.getElementById("divOutput").innerHTML += "<b>Prime factors of " + n2 + "</b><br />";

for (var i = 0; i < primeFactorsArray.length; i++) {
document.getElementById("divOutput").innerHTML += primeFactorsArray[i];

// Prevent extra x
if (i + 1 < primeFactorsArray.length) {
document.getElementById("divOutput").innerHTML += " x ";
}
};

document.getElementById("divOutput").innerHTML += "<br /><b>All factors of " + n2 + "</b><br />";

for (var i = 0; i < allFactorsArray.length; i++) {
document.getElementById("divOutput").innerHTML += allFactorsArray[i] + "<br />";
};
}
</script>

<body>
<div id="divOutput"></div>
</body>
</html>

-

• Something is wrong with the way you generate the different factors. If you try with n=300. You'll see that you miss (at least) : 300 = 6 * 50.

• It's not quite clear to me what you are trying to achieve with the for (var t = 0; t < primeFactorsArray.length; t++) loop. Indeed, as you keep looping, the value of the addFacotr variable will be the one you would get on the primeFactorsArray.length - 1th item. Thus, your loop is doing the same as if (otherFactor == primeFactorsArray[primeFactorsArray.length - 1]) (given the fact that primeFactorsArray.length is greater than 0, which will always be the case).

• As a general rule, always define in the smallest possible scope to make the reading easier.

• You could store only the prime factors to make the second part of the processing easier. Also, you could generate the output string during the process.

You'll find my version of the code here, I have just taken my stylistic comments into account. The algorithm is still wrong here.

-
Yeah... I tried 18 and I got 2 x 9, 3 x 6, 9 x 2. I'm trying to figure out why 2 x 9 was outputted twice. –  user1822824 Jan 16 '13 at 23:24
I've updated my answer. –  Josay Jan 16 '13 at 23:26
I think 300 is not equal to 6 * 500. –  Pointy Mar 2 '14 at 16:25

Have you considered using Pollard's Rho algorithm? It's insanely fast on small integers, and really easy to implement: http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm#Algorithm

-
I want to stick with trial division for now as I am new to this and it's what I used in my script. –  user1822824 Jan 16 '13 at 9:03

This function is pretty fast and simple

function getFactors(integer){
var factors = [],
quotient = 0;

for(var i = 1; i <= integer; i++){
quotient = integer/i;

if(quotient === Math.floor(quotient)){
factors.push(i);
}
}
return factors;
}


getFactors(900) returns: [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 25, 30, 36, 45, 50, 60, 75, 90, 100, 150, 180, 225, 300, 450, 900]

you could easily retrieve matched pairs such as 1x900, 2x450, 3x300 by matching from each end.

-

The number to be factored is hard-coded into your script, making it inflexible. I added a user input so you don't have to rewrite the code.

var userInput = prompt("What number do you want factored?")