Databases
StackOverflow2013
Postsdbo
POSieve of Eratosthenes algorithm in JavaScript running endless for large number
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSieve of Eratosthenes algorithm in JavaScript running endless for large number
    primarykey
    data
    text
    <p>I have been trying to write <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow noreferrer">Sieve of Eratosthenes</a> algorithm in JavaScript. Basically I just literally followed the steps below:</p> <ol> <li>Create a list of consecutive integers from 2 to (n-1)</li> <li>Let first prime number p equal 2</li> <li>Starting from p, count up in increments of p and removes each of these numbers (p and multiples of p)</li> <li>Go to the next number in the list and repeat 2,3,4</li> <li>Add unintentionally deleted prime numbers back to the list</li> </ol> <p>and this is what I have come up with:</p> <pre><code>function eratosthenes(n){ var array = []; var tmpArray = []; // for containing unintentionally deleted elements like 2,3,5,7,... var maxPrimeFactor = 0; var upperLimit = Math.sqrt(n); var output = []; // Eratosthenes algorithm to find all primes under n // Make an array from 2 to (n - 1) //used as a base array to delete composite number from for(var i = 2; i &lt; n; i++){ array.push(i); } // Remove multiples of primes starting from 2, 3, 5,... for(var i = array[0]; i &lt; upperLimit; i = array[0]){ removeMultiples: for(var j = i, k = i; j &lt; n; j += i){ var index = array.indexOf(j); if(index === -1) continue removeMultiples; else array.splice(index,1); } tmpArray.push(k); } array.unshift(tmpArray); return array; } </code></pre> <p>It works for small numbers but not for numbers larger than one million. I used Node.js to test and the process just seems endless and no memory error shown up. I've read a solution <a href="https://stackoverflow.com/a/14041122/165820">here</a>(also in javascript) but still cannot fully comprehend it. </p> <p>Question: How to make this work for sufficiently large numbers such as one million and above?</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USWill Ness
    1. USBao
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POSieve of Eratosthenes algorithm in JavaScript running endless for large number
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POSieve of Eratosthenes algorithm in JavaScript running endless for large number
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POSieve of Eratosthenes algorithm in JavaScript running endless for large number
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYou are making your sieve intentionally slower by making use of `Array#indexOf` and `Array#splice`
      singulars
      1. POSieve of Eratosthenes algorithm in JavaScript running endless for large number
      1. USAlexander
    2. COYour function returns [[2],3] instead of [2,3] on input of 5...
      singulars
      1. POSieve of Eratosthenes algorithm in JavaScript running endless for large number
      1. USloxxy
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload