Skip to content

Instantly share code, notes, and snippets.

@jonarnaldo
Created February 25, 2014 04:32
Show Gist options
  • Select an option

  • Save jonarnaldo/9202749 to your computer and use it in GitHub Desktop.

Select an option

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
Copy Markdown

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