
The use of prime numbers is everywhere in computer science... in fact you're using them right now to connect to this website, read your email and send text messages.
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));