Created
February 25, 2014 04:32
-
-
Save jonarnaldo/9202749 to your computer and use it in GitHub Desktop.
Javascript Sieve of Eratosthenes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
}); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Can you please explain the time complexity as well.