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:
## 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.
## 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

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.
// 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)

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

3

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

I had a go at a solution in Java (It works but perhaps could be made more efficient)

public class EratosthenesAlgorithm { public List<Integer> getPrimeNumbersUpTo(Integer n){ List<Integer> primeNumbers = getNumbersFromTwoToN(n); int index = 0; Integer upTo = primeNumbers.get(index); while(true) { primeNumbers = getCollect(primeNumbers, upTo); primeNumbers.size(); index = primeNumbers.indexOf(upTo) + 1; if (index == primeNumbers.size()){ break; } upTo = primeNumbers.get(index); } return primeNumbers; } private List<Integer> getCollect(List<Integer> aAllNumbers, Integer aUpTo) { return aAllNumbers.stream().filter(p -> ((p % aUpTo) != 0) || (p == aUpTo)).collect(Collectors.toList()); } private List<Integer> getNumbersFromTwoToN(Integer n){ ArrayList<Integer> numbersUpToN = new ArrayList<>(); for(int i = 2; i<= n; i++){ numbersUpToN.add(i); } return numbersUpToN; } }

anjumabbas

commented on 02/23/19

0

Instead of traversing again it would be better if
We can append an element into array of prime
At the start where it is checked if if b[i-2] is true.

oorja

commented on 02/05/19

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

gabrieldefazio

commented on 08/01/17

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

def prim(n): b = list(range(1, n)) for i in range(2, n): if b[i-2]: for j in range(2*i, n+1, i): b[j - 2] = False yield i print(list(prim(100)))

atashfeshan

commented on 10/11/18

Log in to submit a comment.