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">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<title>All Factors 1</title>
<script>
window.onload = function() {
// 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();
var addFactor = true;
// 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
addFactor = false;
} else {
addFactor = true;
}
}
if (addFactor == true) {
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>
</head>
<body>
<div id="divOutput"></div>
</body>
</html>
4 Answers 4
A few comments :
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 theaddFacotrvariable will be the one you would get on theprimeFactorsArray.length - 1th item. Thus, your loop is doing the same asif (otherFactor == primeFactorsArray[primeFactorsArray.length - 1])(given the fact thatprimeFactorsArray.lengthis 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.
-
\$\begingroup\$ 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. \$\endgroup\$user1822824– user18228242013年01月16日 23:24:33 +00:00Commented Jan 16, 2013 at 23:24
-
\$\begingroup\$ I've updated my answer. \$\endgroup\$SylvainD– SylvainD2013年01月16日 23:26:04 +00:00Commented Jan 16, 2013 at 23:26
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
-
\$\begingroup\$ I want to stick with trial division for now as I am new to this and it's what I used in my script. \$\endgroup\$user1822824– user18228242013年01月16日 09:03:46 +00:00Commented Jan 16, 2013 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?")
window.onload = function() {
// Find all factors
var n = userInput;
// etc.