Interview Questions

  • View all interview questions
  • blank
  • Generate primes up to N using the sieve of Eratosthenes algorithm
    The sieve of Eratosthenes algorithm generates all the primes up to a given limit. This is a common and fast algorithm used to generate a list of primes up to a given limit. It works by making a list from 1 to N, and then iterating through the list and progressively removing non-prime, composite numbers until only primes are left in a list.

    Example

    For example, if we wanted to generate all the primes up to the number 30, we first create a list of numbers from 1 to 30 and follow the numbered steps: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 (Step 1) The algorithm starts at the first number, 1, and removes it because it is not a prime number. (Step 2) The next number is 2, which is a prime so it stays, but now all multiples of 2 are removed from the list: 4, 6, 8, 10, etc. 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 (Step 3) The next number is 3, which is a prime so it stays, but now all multiples of 3 are removed from the list: 6, 9, etc. 2 3 5 7 11 13 17 19 23 25 29 (Step 4) The next number is 5, which is a prime so it stays, but now all multiples of 5 are removed from the list: 10, 15, etc. 2 3 5 7 11 13 17 19 23 29 (Step 5) All the numbers now, 7, 11, 13, etc., are all primes and there are no more multiples of numbers we can remove from the list, so we are done and the list that is left is our list of primes.

    Solution

    We will create a function called sieve that will take a limit as a parameter, generate a list of numbers from 1 to limit, and then remove all composite numbers as it loops from 1 to limit.
    // our sieve function which will return a list of primes
    // up to the limit argument passed
    function sieve(limit) {
     
      var bools = [];
      var primes = [];
    
      // generate a list of booleans all set to true initially
      // the array is indexed from 2 to limit representing all numbers
      // e.g. [true, true, true, true] = [2, 3, 4, 5]
      for (var i = 1; i < limit; i++) { bools.push(true); } 
    
      // loop from 2 to limit setting the composite numbers to false
      // we start from 2 because we know 1 is not a prime number
      for (var i = 2; i < limit; i++) {
        if (bools[i-2]) {
          for (var j = i*2; j <= limit; j += i) {
            bools[j-2] = false;    
          }
        }
      }
      
      // now generate the list of primes only where
      // there is a true value in the bools array
      for (var p = 0; p < bools.length; p++) {
        if (bools[p]) { primes.push(p+2); }
      }
      
      return primes;
    
    } 
    
    sieve(30);
    
    def sieve(limit):
      
      bools = []
      primes = []
      
      # generate a list of booleans all set to True initially
      # the list is indexed from 2 to limit representing all numbers
      # e.g. [True, True, True, True] = [2, 3, 4, 5]
      for i in range(1, limit):
        bools.append(True)
        
      # loop from 2 to limit setting the composite numbers to False
      # we start from 2 because we know 1 is not a prime number
      for i in range(2, limit):
        if bools[i-2]:
          for j in range(i*2, limit+1, i):
            bools[j-2] = False
            
      # now generate the list of primes only where
      # there is a True value in the bools list
      for p in range(0, len(bools)):
        if (bools[p]):
          primes.append(p+2)
          
      return primes
        
    print sieve(6)           
    
    Run Code
    Run Code

    Running time

    The running time of this algorithm without any optimizations is O(n log log n). The proof of this requires understanding the prime harmonic series and the fact that it converges to (log log n), but a detailed explanation can be found here.

    Common optimizations

    Some common ways to improve the algorithm are: (1) No need to store even numbers at all because they cannot be primes (2) Instead of looping from 2 to N and checking each number, you can loop to √N [1]

    Sources

    http://www.careercup.com/question?id=11367823
    mrdaniel published this on 11/9/15 | prime, math, array, Amazon, Fullstack Academy
    Comments
  • +
  • 1
  • -
  • To display code include the following tags:
    
    function primes(n){
      var arr = [];
      for(var i = 2; i <= n; i++){
        if(i !== 4 && i <= 5){
         arr.push(i);
        }
        else {
          if(i > 5 && i % 2 !== 0 && i % 3 !== 0 && i %  5 !== 0) {
            arr[arr.length] = i;
          }
        }
      }
      return arr;
    }
    
  • +
  • 1
  • -
  • @annabrown: The reason for bools[i - 2] is because bools, at the end of this algorithm, will have "true" values in the spots that are prime numbers. But the bools array starts at the number 2, because the first prime is 2, so the bools array essentially stands for: [2, 3, 4, 5, ...]. When we are within the for loop and are at i = 2 for example, we want the first potential prime number which is 2, but we cannot do bools[i] because then we get the number 4. So to correct this we subtract 2 to get the i value and the prime number matched up properly, i.e. i = 2 bool[2 - 2] = 2 i = 3 bool[3 - 2] = 3 i = 4 bools[4 - 2] = 4 etc. Hope this clears it up!
  • +
  • 0
  • -
  • To display code include the following tags:
    function allPrimes(n){
      let range = [...Array(n+1).keys()].slice(2)
      return range.filter(number=>isPrime(number))
      function isPrime(number){
        for (let i = 2; i<Math.sqrt(number); i++){
          if (!(number%i)) return false
        }return true
      }
    }
  • +
  • 0
  • -
  • To display code include the following tags:
    
    function primes(n){
      var arr = [];
      for(var i = 2; i <= n; i++){
        if(i >= 2 && i !== 4 && i <= 5){
         arr.push(i);
        }
        else {
          if(i > 5 && i % 2 !== 0 && i % 3 !== 0 && i %  5 !== 0) {
            arr[arr.length] = i;
          }
        }
      }
      return arr;
    }
    
    
  • +
  • 0
  • -
  • Hey mrdaniel! I'm struggling to understand the conditional statement "bools[i-2]" . Why does it require me to subtract 2 from the index of i, and j later on in the next loop? Also in the third loop, why does it require me to add (p + 2) when pushing the prime numbers to the primes array? I feel like there is an understanding of prime numbers that I am missing! Thank you!
    Login to submit a comment