Calculating Prime Numbers

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

<span class="hljs-comment">//Sieve of Eratosthenes</span>
<span class="hljs-keyword">const</span> <span class="hljs-title function_">sieve</span> = (<span class="hljs-params">n</span>) =&gt; {
  <span class="hljs-keyword">var</span> grid = {};
  <span class="hljs-keyword">for</span> (<span class="hljs-keyword">var</span> i = <span class="hljs-number">2</span>; i &lt;= n; i++) {
    grid[i]={<span class="hljs-attr">marked</span>: <span class="hljs-literal">false</span>};
  }
  <span class="hljs-keyword">const</span> limit = <span class="hljs-title class_">Math</span>.<span class="hljs-title function_">sqrt</span>(n);
  <span class="hljs-keyword">for</span> (<span class="hljs-keyword">var</span> i = <span class="hljs-number">2</span>; i &lt;= limit; i++) {
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">var</span> x = i + i; x &lt;= n; x += i){
      grid[x].<span class="hljs-property">marked</span> = <span class="hljs-literal">true</span>;
    }
  }
  <span class="hljs-keyword">var</span> out =[];
  <span class="hljs-keyword">for</span> (<span class="hljs-keyword">var</span> i = <span class="hljs-number">2</span>; i &lt;= n; i++) {
    <span class="hljs-keyword">if</span>(!grid[i].<span class="hljs-property">marked</span>) out.<span class="hljs-title function_">push</span>(i);
  }
  <span class="hljs-keyword">return</span> out;
};
<span class="hljs-variable language_">console</span>.<span class="hljs-title function_">log</span>(<span class="hljs-title function_">sieve</span>(<span class="hljs-number">100</span>));