Skip to content

Instantly share code, notes, and snippets.

@jonarnaldo
Created February 25, 2014 04:32
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jonarnaldo/9202749 to your computer and use it in GitHub Desktop.
Save jonarnaldo/9202749 to your computer and use it in GitHub Desktop.
Javascript Sieve of Eratosthenes
var Eratosthenes = function (n) {
this.array = function () {
var arr = [];
var output = [];
for (var i = 0; i < n; i++) {
arr.push(i);
}
return arr;
};
this.sieve = function () {
var sieve = this.array();
var limit = Math.sqrt(n);
for (var i = 2; i <= limit; i++) {
if (sieve[i]) {
for (var j = i * i; j < n; j += i) {
sieve[j] = false;
}
}
}
var arr = [];
for (var k = 2; k < sieve.length; k++) {
if (sieve[k]) {
arr.push(sieve[k]);
}
}
return arr;
};
};
$("input").keypress(function (e) {
if (e.which == 13) {
var input = $("#input").val();
var era = new Eratosthenes(input);
var sieve = era.sieve().join(" ");
$("#output").html(sieve);
}
});
@bharathmuppa
Copy link

Can you please explain the time complexity as well.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment