stick_branch

10-19-2008, 06:12 AM

Hi, I was trying to put an implementation of Eratosthenes sieve (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) into a web app. It currently stores all the values to an array primefactors. The aim is to leave the array with only prime factors left.

I know searching arrays is an expensive op that i would rather avoid, but splice doesn't seem like the fastest way. I've come to a few paths...

One, I could replace non-primes with "0" or NaN, sort, find the max, find it's position in the array, and delete all the numbers after that...

Or two, i could delete each number by searching inside the array for where it is located. My current code is:

for(i=1;i<=max;i++)

{

primefactor[add]=i;

add++;

}

squareroot=Math.sqrt(max);

for (test=2;test<=squareroot;test++)

{

limit=(max/test);

// Eliminating numbers

for (i=2;i<=limit;i++)

{

a=((i*test)-1);

d++;

primefactor.splice(a,1,0);

}}

But the obvious error in the code is that it will delete the element from the array, and on the second loop will cull the wrong numbers. Is there any other options to delete the non-prime factors or which option would be fastest? I'm sure that searching for each string would be very costly.

Or am i going about the sieve (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) the completely wrong way. Thanks guys!

Stick.

I know searching arrays is an expensive op that i would rather avoid, but splice doesn't seem like the fastest way. I've come to a few paths...

One, I could replace non-primes with "0" or NaN, sort, find the max, find it's position in the array, and delete all the numbers after that...

Or two, i could delete each number by searching inside the array for where it is located. My current code is:

for(i=1;i<=max;i++)

{

primefactor[add]=i;

add++;

}

squareroot=Math.sqrt(max);

for (test=2;test<=squareroot;test++)

{

limit=(max/test);

// Eliminating numbers

for (i=2;i<=limit;i++)

{

a=((i*test)-1);

d++;

primefactor.splice(a,1,0);

}}

But the obvious error in the code is that it will delete the element from the array, and on the second loop will cull the wrong numbers. Is there any other options to delete the non-prime factors or which option would be fastest? I'm sure that searching for each string would be very costly.

Or am i going about the sieve (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) the completely wrong way. Thanks guys!

Stick.