Method of deleting elements from an array

stick_branch · 10-19-2008, 06:12 AM

Hi, I was trying to put an implementation of Eratosthenes sieve 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:

Code:

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 the completely wrong way. Thanks guys!

Stick.

BubikolRamios · 10-19-2008, 07:17 AM

make another array,

loop thru first
another.push(whatewer u want from first array).

stick_branch · 10-19-2008, 07:26 AM

Quote:

Originally Posted by BubikolRamios

make another array,

loop thru first
another.push(whatewer u want from first array).

I see how it works in theory, but for the sieve to work i have to delete values from the array to find the primes... e.g. this works:

Code:

for (test=2;test<=squareroot;test++)
{
limit=(max/test);
// Eliminating numbers
for (i=2;i<=limit;i++)
{
a=((i*test)-1);
if(primefactor[a]!=0)
{
d++;
}

primefactor.splice(a,1,0);
}}

function sortBack(b,a)
{
return a - b;
}
e=(max-d);
primefactor.sort(sortBack);
primefactor.splice(e,d);

But i'd rather kill the if loop than keep it there.

liorean · 10-19-2008, 07:43 AM

Here's one way of doing the sieve:

Code:

function sieve(upto){
    var
        i=2,
        j,
        k,
        o=[]; // You don't need this to be an array, it can be a regular object

    if(upto<2 || upto!==(upto>>0))
        throw'Argument upto should be an integer > 2';

    // Set up a contigious number list from 2 to upto
    do
        o[i]=i;
    while(upto>i++);

    // Cull the list of non-primes
    for(i in o){
        k=i>>0; // Making sure k is an integer and not a string
        j=k*k;
        if(j>upto) // All remaining elements are primes
            break;
        do
            delete o[j]; // Start culling at i squared
        while((j+=k)<=upto)
    }
    return o;
}

oesxyl · 10-19-2008, 09:00 AM

try also this:

Code:

<?xml version="1.0"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    <title>prime tests</title>
    <script type="text/javascript">//<![CDATA[
    var primeset = [2, 3, 5, 7, 11, 13];

    function isprime(thisnum){
       var i;
       thisnum = parseInt(thisnum);
       if(primeset.indexOf(thisnum) == -1){
          // is not in sieve, could be prime
          var maxfactor = Math.round(Math.sqrt(thisnum));
          var maxprime = primeset.pop();
          primeset.push(maxprime);
          if(maxfactor > maxprime){
             // we must find all other primes between maxprime exclusive and maxfactor inclusive
             for(i=maxprime+2;i<=maxfactor;i+=2){
                if(isprime(i)){
                   primeset.push(i);
                }
             }
          }
          // now we can check if is prime
          for(i in primeset){
            if(thisnum % primeset[i] == 0){
               return false;
            }
          }
       }
       return true;
    }
    //]]></script>
  </head>
  <body>
    <p><script type="text/javascript">//<![CDATA[
    var p;
//    for(p=160000;p<200000;p++){
    for(p=1600;p<=2000;p++){
       if(isprime(p)){
          document.write(p + " is ");
       }else{
          document.write(p + " is not ");
       }
       document.write("prime <br/>");
    }
    document.write('in primeset we have:<br/>');
    for(p in primeset){
       document.write(primeset[p] + ", ");
    }
    document.write('<br/>');
    //]]></script></p>
  </body>

</html>

the speed could be improved,

best regards

oesxyl · 10-19-2008, 09:05 AM

Quote:

Originally Posted by stick_branch

I see how it works in theory, but for the sieve to work i have to delete values from the array to find the primes... e.g. this works:

not necesarrely "delete",

try to replace with "mark somehow", that means you can put them in a array and reuse later or something else. See the code I posted.

best regards