Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 6 of 6
  1. #1
    New Coder
    Join Date
    Oct 2008
    Location
    Australia
    Posts
    32
    Thanks
    1
    Thanked 1 Time in 1 Post

    Method of deleting elements from an array

    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.
    Last edited by stick_branch; 10-19-2008 at 07:36 AM.

  • #2
    Senior Coder
    Join Date
    Dec 2005
    Location
    Slovenia
    Posts
    1,988
    Thanks
    120
    Thanked 76 Times in 76 Posts
    make another array,

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

  • #3
    New Coder
    Join Date
    Oct 2008
    Location
    Australia
    Posts
    32
    Thanks
    1
    Thanked 1 Time in 1 Post
    Quote Originally Posted by BubikolRamios View Post
    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.

  • #4
    Master Coder
    Join Date
    Feb 2003
    Location
    Umeå, Sweden
    Posts
    5,575
    Thanks
    0
    Thanked 83 Times in 74 Posts
    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;
    }
    Last edited by liorean; 10-19-2008 at 08:59 AM.
    liorean <[lio@wg]>
    Articles: RegEx evolt wsabstract , Named Arguments
    Useful Threads: JavaScript Docs & Refs, FAQ - HTML & CSS Docs, FAQ - XML Doc & Refs
    Moz: JavaScript DOM Interfaces MSDN: JScript DHTML KDE: KJS KHTML Opera: Standards

  • #5
    Master Coder
    Join Date
    Dec 2007
    Posts
    6,682
    Thanks
    436
    Thanked 890 Times in 879 Posts
    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 &#37; 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

  • #6
    Master Coder
    Join Date
    Dec 2007
    Posts
    6,682
    Thanks
    436
    Thanked 890 Times in 879 Posts
    Quote Originally Posted by stick_branch View Post
    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


  •  

    Tags for this Thread

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •