Just released - The Imposter's Roadmap!

### Calculating Prime Numbers

You can access this course in just a minute, and support my efforts to rid the world of crappy online courses!

This problem has been solved (rather elegantly I might add) over 2200 years ago by a chap named Eratosthenes. His algorithm is so elegant that just about anyone can understand it. In mathematical terms, his algorithm uses a sieve to filter and extract the numbers in a set:

Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The primordial example of a sifted set is the set of prime numbers up to some prescribed limit X.

How would you solve this problem? Also: would you consider this dynamic programming? We’ll answer the latter question at the very end.

## The Code

``````//Sieve of Eratosthenes
const sieve = (n) => {
var grid = {};
for (var i = 2; i <= n; i++) {
grid[i]={marked: false};
}
const limit = Math.sqrt(n);
for (var i = 2; i <= limit; i++) {
for(var x = i + i; x <= n; x += i){
grid[x].marked = true;
}
}
var out =[];
for (var i = 2; i <= n; i++) {
if(!grid[i].marked) out.push(i);
}
return out;
};
console.log(sieve(100));
``````