added "Sieve of Eratosthenes" - Simple, ancient algorithm for finding all prime numbers up to any given limit

pvoznenko · pvoznenko · commit 75f6d516b69d · 2015-01-11T13:56:52.000+01:00
diff --git a/.gitignore b/.gitignore
@@ -1,3 +1,4 @@
 node_modules
 npm-debug.log
-debug
+debug
+.idea
diff --git a/gulpfile.js b/gulpfile.js
@@ -6,7 +6,7 @@ var gulp = require('gulp'),
     stylish = require('jshint-stylish');
 
 gulp.task('jsdoc', shell.task([
-  './node_modules/.bin/jsdoc -c ./doc-config.json',
+  './node_modules/.bin/jsdoc -c ./doc-config.json'
 ]));
 
 gulp.task('lint', function () {
diff --git a/src/primes/sieve-of-eratosthenes.js b/src/primes/sieve-of-eratosthenes.js
@@ -0,0 +1,50 @@
+/**
+ * Sieve of Eratosthenes
+ *
+ * Simple, ancient algorithm for finding all prime numbers up to any given limit
+ */
+(function (exports) {
+    'use strict';
+
+    /**
+     * Returns Sieve of Eratosthenes for specified number
+     *
+     * Simple, ancient algorithm for finding all prime numbers up to any given
+     * limit
+     *
+     * @param {Number} limit - algorithm will return list with prime numbers up
+     *                         to given limit
+     *
+     * @returns {Array} - will return array with all prime numbers up to
+     *                    provided limit
+     */
+    exports.sieveOfEratosthenes = function (limit) {
+        var sieve = [],
+            primes = [], k, l;
+
+        sieve[1] = false;
+
+        for (k = 2; k <= limit; k += 1) {
+            sieve[k] = true;
+        }
+
+        for (k = 2; k * k <= limit; k += 1) {
+            if (sieve[k] !== true) {
+                continue;
+            }
+
+            for (l = k * k; l <= limit; l += k) {
+                sieve[l] = false;
+            }
+        }
+
+        sieve.forEach(function (value, key) {
+            if (value) {
+                this.push(key);
+            }
+        }, primes);
+
+        return primes;
+    };
+
+}(typeof exports === 'undefined' ? window : exports));
diff --git a/test/primes/sieve-of-eratosthenes.spec.js b/test/primes/sieve-of-eratosthenes.spec.js
@@ -0,0 +1,17 @@
+'use strict';
+
+var sieveOfEratosthenes =
+    require('../../src/primes/sieve-of-eratosthenes').sieveOfEratosthenes;
+
+describe('Sieve Of Eratosthenes', function () {
+    it('should give the right sequence of primes for limit 12', function () {
+        expect(sieveOfEratosthenes(12).toString())
+            .toBe([2, 3, 5, 7, 11].toString());
+    });
+
+    it('should give the empty list for limit less or equal 1', function () {
+        expect(sieveOfEratosthenes(-12).toString()).toBe([].toString());
+        expect(sieveOfEratosthenes(0).toString()).toBe([].toString());
+        expect(sieveOfEratosthenes(1).toString()).toBe([].toString());
+    });
+});

-Original file line number
+Diff line change
@@ @@ -1,3 +1,4 @@ @@
 node_modules
 npm-debug.log
 -debug
 +debug
 +.idea