Interview Questions

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.

You need to be a premium member to see the rest of this question and code.

mrdaniel
published this on 11/9/15 **|**

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; }

bpaksoy

commented on 12/09/16

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!

mrdaniel

commented on 05/27/16

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!

annabrown

commented on 05/27/16

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; }

bpaksoy

commented on 12/09/16

Login to submit a comment