0
\$\begingroup\$

I am trying to factor integers using the trial division algorithm (Wikipedia: http://en.wikipedia.org/wiki/Trial_division).

I reviewed the Wikipedia entry for trial division and multiple other sources but I don't completely understand the trial division algorithm.

I wrote the code below based on my findings and it finds all of the prime factors of a number.

For example, input 20 and you get its prime factors 2 2 5. I would like to know if it can be simplified or better written (I want to stick with the trial division algorithm --- I don't plan on inputting numbers any larger than 9,999)?

    <!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>Prime Number Checker</title>
<script>
window.onload = function() {
    // All the prime numbers under 1000
    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];

    // Find prime factors
    var n = 20;

    var primeFactors = "";

    // Trial division algorithm
    for (var i = 0; primeNumbers[i] < n; i++) {
        if (n % primeNumbers[i] == 0) {         
            var temp = n;

            while (temp % primeNumbers[i] == 0) {
                temp = temp / primeNumbers[i];
                primeFactors += " " + primeNumbers[i] + " ";
            }
        }
    }

    document.getElementById("divSolution").innerHTML = primeFactors;
}
</script>
</head>

<body>
<div id="divSolution"></div>
</body>
</html>
\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

A few comments :

  1. Before writing any code, perform the computation manually. How would you do it for 20? You'd do something along the lines like :

    • let's try the first prime number : 2
    • is 2 a divisor of 20 ? yes, it is. 20 is 2*10 so let's add 2 to the list of divisors and let's focus on 10 now.
    • is 2 a divisor of 10 ? yes, it is. 10 is 2*5 so let's add 2 to the list of divisors and let's focus on 5 now.
    • let's consider the next prime number. It's 3. Oh, 3*3 is actually bigger than 5 so we won't be able to find any other prime factor smaller than 5 : let's add 5 to the list of divisors.
    • Try it yourself with numbers such a 8, 100, 19....

  2. Then, about your code : the first is I noticed that your loop condition is not right and you might get out of your array. Just try a value of n greater than 168 and you'll probably notice the issue.

If you want to follow the wiki page and to something like : for p in primes: if p*p > n: break what you really need to do is.

// Find prime factors
var n = 180;
var primeFactors = "";
// Trial division algorithm
for (var i = 0, p=primeNumbers[i]; i < primeNumbers.length && p*p<=n; i++, p=primeNumbers[i]) {
    while (n % p == 0) {         
            primeFactors += " " + p + " ";
            n/=p;
    }
}
if (n>1)
{
    primeFactors += " " + n + " ";
}

document.getElementById("divSolution").innerHTML = primeFactors;

(Sorry for rewriting the whole code)

\$\endgroup\$

Your Answer

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

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