primes/sieve-of-eratosthenes.js

  1. (function (exports) {
  2.   'use strict';
  4.   /**
  5.    * Sieve of Eratosthenes.
  6.    *
  7.    * Simple, ancient algorithm for finding all prime numbers up to given limit.
  8.    *
  9.    * Returns list of primes up to specified limit.
  10.    *
  11.    * For example, for limit 10 it should return following list of primes:
  12.    * [2, 3, 5, 7].
  13.    *
  14.    * @module primes/sieve-of-eratosthenes
  15.    * @param {Number} limit - Algorithm will returns list of primes up to
  16.    * specified limit.
  17.    * @returns {Array} Will return list with all prime numbers up to provided.
  18.    * limit.
  19.    *
  20.    * @example
  21.    * var sieveOfEratosthenes =
  22.    * require('path-to-algorithms/src/sieve-of-eratosthenes').sieveOfEratosthenes;
  23.    *
  24.    * console.log(sieveOfEratosthenes(12)); // [2, 3, 5, 7, 11]
  25.    */
  26.   exports.sieveOfEratosthenes = function (limit) {
  27.     var sieve = [];
  28.     var primes = [];
  29.     var k;
  30.     var l;
  32.     sieve[1] = false;
  34.     for (k = 2; k <= limit; k += 1) {
  35.       sieve[k] = true;
  36.     }
  38.     for (k = 2; k * k <= limit; k += 1) {
  39.       if (sieve[k] !== true) {
  40.         continue;
  41.       }
  43.       for (l = k * k; l <= limit; l += k) {
  44.         sieve[l] = false;
  45.       }
  46.     }
  48.     sieve.forEach(function (value, key) {
  49.       if (value) {
  50.         this.push(key);
  51.       }
  52.     }, primes);
  54.     return primes;
  55.   };
  57. }(typeof exports === 'undefined' ? window : exports));