2
\$\begingroup\$

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>
Improve this question
\$\endgroup\$

4 Answers 4

Reset to default
4
\$\begingroup\$

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 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.

Improve this answer
\$\endgroup\$
2
  • \$\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
    Jan 16, 2013 at 23:24
  • \$\begingroup\$ I've updated my answer. \$\endgroup\$
    – SylvainD
    Jan 16, 2013 at 23:26
1
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
1
  • \$\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
    Jan 16, 2013 at 9:03
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.