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

## 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 |
• +
• 2
• -
• ``` 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
• -
• 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!
• +
• 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
• -
• ```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)))```
• +
• 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.
• +
• 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; } }```