CODEWITHSUNDEEP
javascriptperformanceloopsfor-loop
Jakov Maršić
Jakov Maršić

Reputation: 13

Is there any way to increase performance for this for loop in JS?

Im trying to solve project euler 10 problem (find the sum of all the primes below two million), but the code takes forever to finish, how do i make it go faster?

    console.log("Starting...")
var primes = [1000];
var x = 0;
var n = 0;
var i = 2;
var b = 0;
var sum = 0;

for (i; i < 2000000; i++) {
    x = 0;
    if (i === 2) {
            primes[b] = i
            sum += primes[b];
            console.log(primes[b]);
            b++;
        }
    for (n = i - 1; n > 1; n--) {
        if (i % n === 0) {
            x++;
        }
        if (n === 2 && x === 0) {
            primes[b] = i;
            sum += primes[b];
            console.log(primes[b]);
            b++;
        }

    }
}
console.log(sum)

Upvotes: 1

Views: 95

Answers (3)

lex82
lex82

Reputation: 11297

Since you keep an array of your primes anyway, you can split the process in two steps:

  • Generating the primes up to your limit of 2 million
  • and summing up.

As pointed out by others, you need only check whether a candidate number is divisable by another prime not larger than the square root of the candidate. If you can write a number as a product of primes, then one of those primes will always be lower than or equal to the number's square root.

This code can be optimized further but it is several orders of magnitude faster than your initial version:

function primesUpTo(limit) {
    if (limit < 2) return [];

    var sqrt = Math.floor(Math.sqrt(limit));
    var testPrimes = primesUpTo(sqrt);
    var result = [].concat(testPrimes);

    for (var i=sqrt+1 ; i<=limit ; i++) {
        if (testPrimes.every(function(x) { return (i % x) > 0 })) {
            result.push(i);
        }
    }
    return result;

}

var primes = primesUpTo(2000000);
var sum = primes.reduce(function(acc, e) { return acc + e });

Upvotes: 0

lex82
lex82

Reputation: 11297

Here is another version based on the Sieve of Eratosthenes. It requires much more memory but if this does not concern you it's also pretty fast.

// just a helper to create integer arrays
function range(from, to) {
    var numbers = [];
    for (var i=from ; i<=to ; i++) {
        numbers.push(i);
    }
    return numbers;
}

function primesUpTo(limit) {
    if (limit < 2) return [];

    var sqrt = Math.floor(Math.sqrt(limit));
    var testPrimes = primesUpTo(sqrt);
    var numbers = range(sqrt+1, limit);
    testPrimes.forEach(function(p) {
        numbers = numbers.filter(function(x) { return x % p > 0 });
    });
    return testPrimes.concat(numbers); 
}

var primes = primesUpTo(2000000);
var sum = primes.reduce(function(acc, e) { return acc + e });

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59154

The biggest super easy things you can do to make this a lot faster:

  • Break out of the inner loop when you find a divisor!

  • When you're checking for primality, start with the small divisors instead of the big ones. You'll find the composites a lot faster.

  • You only have to check for divisors <= Math.sqrt(n)

  • You only need to check prime divisors. You have a list of them.

  • Process 2 outside the loop, and then only do odd numbers inside the loop: for(i=3;i<2000000;i+=2)

Upvotes: 5

Related Questions