I am trying to solve Q10 from Project Euler. I am using JavaScript and Sieve of Atkins algorithm to solve the problem. When I run the code on browsers(Safari and FF) the browsers prompts that the script is unresponsive. Even if I let the script to continue I never got the answer. I know there are threads for the same Project Euler problem.

My questions would be:-

1.How far JavaScript is capable to solve such plex mathematical problems for browsers?

2.Is there any other environment where I can I test my JavaScript programs?

Thank you All.

I am trying to solve Q10 from Project Euler. I am using JavaScript and Sieve of Atkins algorithm to solve the problem. When I run the code on browsers(Safari and FF) the browsers prompts that the script is unresponsive. Even if I let the script to continue I never got the answer. I know there are threads for the same Project Euler problem.

My questions would be:-

1.How far JavaScript is capable to solve such plex mathematical problems for browsers?

2.Is there any other environment where I can I test my JavaScript programs?

Thank you All.

• javascript

• 1 You might want to use web workers (HTML5); they run in a separate thread so as not to let your browser freeze. Concerning JavaScript speed, this changes everyday with the browser updates... – pimvdb Commented Jul 22, 2011 at 12:07
• 1 This sounds like a job for node.js. Or you could write it in some other scripting language to see if it finishes, and then convert it to JavaScript. – Pat Commented Jul 22, 2011 at 12:09
• 1 It's definitely possible with the right algorithm. If it freezes (for longer than a few seconds), your algorithm is just not good enough yet. – user395760 Commented Jul 22, 2011 at 12:11
• 1 Isn't Atkins a bit overkill? For the numbers smaller than two millions even a brute force approach in javascript (just looping over all odd numbers starting at 3 and check if they're prime) solves the question in about one second on chrome... – 6502 Commented Jul 22, 2011 at 12:23

4 Answers 4

1. I would have thought as capable as any other - JavaScript implementations have been optimised a lot in recent years thanks to increased used in the web.

2. You can use either node.js or CScript (a mand line version of the Windows Script host - this is supplied as part of Windows).

If I remember my implementation of that question (in Python) was significantly slower than I thought it would be. The chances are the slowness is due to your algorithm rather than the language.

The goal of project Euler is to get you thinking, mathematically. Think of brute forcing, and you will be stuck. Here is an implementation of the Sieve of Eratosthenes

function problem10() {

    var i, j, k, l = Math.floor((2000000-1)/2), a = [];
    for (i = 0; i < l; i++) {
        a[i] = true;
    } var m = Math.sqrt(2000000);
    for (i = 0; i <= m; i++) {
        if (a[i]) {
            j = 2 * i + 3;
            k = i + j;
            while (k < l) {
                a[k] = false;
                k += j;
            }
        }
    } var s = 2;
    for (i = 0; i < l; i++) {
        if (a[i]) {
            s += 2 * i + 3;
        }
    }
    return s;

}

var d1 = new Date().getTime();
var answer = problem10();
var d2 = new Date().getTime();

console.log('Answer:' + answer + ' time:' + (d2 - d1));

You can run it on the chrome developer's console (Ctrl + Shift + J). And guess what, it clocks 0.1 second.

function problem10(){

    var a = 0;

    function isPrime(n){
        var i = 2;
        var b = true;
        while(i<=Math.sqrt(n) && b){
            b = n%i===0?false:true;
            i++;
        }
        return n<2?false:b;
    }

    for(i=0;i<2000000;i++){
        if(isPrime(i)){
            a+=i;
        }
    }
    return a;

}

You could try testing your implementation on node.js.

However, I would bet that you have a problem with your code. JavaScript in a modern browser is pretty quick (and generally you should get Project Euler answers very quickly; it's not designed to require high amounts of puting power).