CODEWITHSUNDEEP
javascriptprimesprime-factoring
steedsnisps
steedsnisps

Reputation: 125

How to make my code less slow (JavaScript) - largest prime factor

I intend to find the largest prime factor of a number n in Javascript. However, i think this code is to slow or could be sortened, but i dont see how. The point would be to display the last element of the arrayfactors, which would be the largest factor. Anyone have any tips on how I could shorten this? The problem is that my browser notifies me the page is taking too long to respond for a 12 digit number. Should I perhaps not use an array?

function biggest(n) {
// Makes a list of primes smaller than n
var primes = [2];
for (i=3; i < n ; i++) {
    var j=0;
    while (j<primes.length) 
    {   var quotient = i/primes[j];
    if (quotient !== Math.floor(quotient)) 
            {var hasDivisor = false;
            j++;
            }

        else
            {var hasDivisor = true;
            j=primes.length+1;
            }

    }

    if (hasDivisor == false) 
        {primes.push(i);}
} 


// Makes a list of factors
var factors = [];
for (i=0; i<primes.length; i++) {
    var quotient = n/primes[i];

    if (quotient==Math.floor(quotient)) {

        factors.push(primes[i]);}
}
    if (factors.length==0) {
    factors.push(1);
}


    items.push("De biggest factor is "+ factors[factors.length-1] +"!"); 



}

Upvotes: 1

Views: 106

Answers (1)

user448810
user448810

Reputation: 17876

You only need a list of primes up to the square root of n, because if n = p * q, one or the other of p or q must be less than the square root of n (except when n is a perfect square). And instead of computing the primes by iterating over all possible divisors, it is much faster to use the Sieve of Eratosthenes; in pseudocode:

function primes(n)
    ps := []
    sieve := makeArray(2..n, True)
    for p from 2 to n
        when sieve[p]
            append p to ps
            for i from p*p to n step p
                sieve[i] := False
    return ps

Upvotes: 2

Related Questions