JavaScript for Project Euler problems

Question

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 complex mathematical problems for browsers?

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

Thank you All.

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, Jul 22 '11 at 12:07
This sounds like a job for [node.js](http://nodejs.org). Or you could write it in some other scripting language to see if it finishes, and then convert it to JavaScript. — Pat, Jul 22 '11 at 12:09
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. — , Jul 22 '11 at 12:11
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, Jul 22 '11 at 12:23

score 6 · Answer 1 · answered Dec 26 '12 at 13:15

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.

Justin · Accepted Answer · 2011-07-22T12:19:12.227

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.
You can use either node.js or CScript (a command 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.

score 3 · Answer 3 · answered Oct 14 '12 at 13:05

3

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;

}

answered Oct 14 '12 at 13:05

Where did you test this did you test it in a browser? wich browser and so on. – Pablo Jomer Oct 14 '12 at 13:09
@PabloKarlsson, I wrote it in chrome. are you having any problems running it? – Oct 20 '12 at 03:59

score 2 · Answer 4 · answered Jul 22 '11 at 12:06

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 computing power).

JavaScript for Project Euler problems

4 Answers4

Linked