Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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>
share|improve this question

1 Answer 1

up vote 2 down vote accepted

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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