Skip to content

Instantly share code, notes, and snippets.

@jakedobkin
Created November 13, 2011 18:14
Show Gist options
  • Save jakedobkin/1362432 to your computer and use it in GitHub Desktop.
Save jakedobkin/1362432 to your computer and use it in GitHub Desktop.
#!/usr/local/bin/node
//NOW WITH NODE.JS
n=2000000;
sumPrimes=0;
myPrimes = new Array();
// set all array values to true
for (i=2;i<=n;i++)
{
myPrimes[i]=true;
}
// sieve of eratosthenes
for (i=2;i<=n/2;i++)
{
if (myPrimes[i])
{
for (j=2*i;j<=n;j+=i)
{
myPrimes[j]=false;
}
}
}
// add up unsieved primes
for (i=2;i<=n;i++)
{
if(myPrimes[i])
{
sumPrimes+=i;
}
}
console.log(sumPrimes);
@djacobs
Copy link

djacobs commented Nov 13, 2011

You can do this with just your middle loop.

First of all, you don't need to initialize your array. I applaud, it's the good thing to do, but it's not necessary. Before you touch values in the array, myPrimes[anything] is false.

Your sieve implementation was basically exactly like mine.

The n/2 trick is good. I didn't do that.

You don't need a separate loop to add up the primes, you can just accrue the sum as you go along.

#!/usr/local/bin/node

max = 2000000;
var sum = 0;
var prime = new Array();

for (iter = 2; iter < max; iter++) {
    if (!prime[iter]) {
        sum += iter;
        for (i = iter*2; i < max; i += iter) {
            prime[i]=1;
        }
    }
}

console.log("The sum is", sum);

@jakedobkin
Copy link
Author

Yes- it is smart to use just one loop!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment