Skip to content

Instantly share code, notes, and snippets.

@pradeep1991singh
Created July 28, 2020 09:34
Show Gist options
  • Save pradeep1991singh/96df42c25eb3680eacb913fad53d97c2 to your computer and use it in GitHub Desktop.
Save pradeep1991singh/96df42c25eb3680eacb913fad53d97c2 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes
<!DOCTYPE html>
<!--[if lt IE 7]> <html class="no-js lt-ie9 lt-ie8 lt-ie7"> <![endif]-->
<!--[if IE 7]> <html class="no-js lt-ie9 lt-ie8"> <![endif]-->
<!--[if IE 8]> <html class="no-js lt-ie9"> <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js"> <!--<![endif]-->
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<title></title>
<meta name="description" content="">
<meta name="viewport" content="width=device-width, initial-scale=1">
<link rel="stylesheet" href="">
<style>
main {
margin: 25px;
}
.hide {
visibility: hidden;
}
.show {
visibility: visible;
}
#output {
word-break: break-word;
}
</style>
</head>
<body>
<!--[if lt IE 7]>
<p class="browsehappy">You are using an <strong>outdated</strong> browser. Please <a href="#">upgrade your browser</a> to improve your experience.</p>
<![endif]-->
<main>
<input id="input"
type="number"
placeholder="Input - only number allowed"
required
/>
<button id="submit">Generate Prime Numbers</button>
<fieldset>
<legend>Output</legend>
<div id="output"></div>
</fieldset>
<div id="loader" class="hide"><h3>Loading...</h3></div>
</main>
<script async defer>
// Sieve of Eratosthenes: Algorithm overview
// 1. Generate an array of booleans from 0 to n
// 2. Mark 0 and 1 false as they are not prime numbers
// 3. Mark numbers from [2...n] true
// 4. Mark multiple of p in prime[2...n] false
// And finally A value in prime[i] will be true if prime otherwise false
function sieveOfEratosthenes (n) {
// 1. generate array of length n
var prime = new Array(n);
// 2. base case: mark prime[0], prime[1] be false (0 and 1 as they are not prime numbers)
prime[0] = false;
prime[1] = false;
// 3. start from prime[2] and mark all to true
for (var i=2; i <= n; i++) {
prime[i] = true;
}
// 4. Mark multiple of p in prime[2...n] to false
for (var p = 2; p*p <= n; p++) {
// if prime[p] is not changed, then it is a prime
if (prime[p]) {
// update all multiples of p
for (var j = p*p; j <= n; j += p) {
prime[j] = false;
}
}
}
// return table
return prime;
}
function getPrimeNumbers (number) {
var primeTable = sieveOfEratosthenes(number);
return primeTable.map((p, i) => {
if (p) return i
}).filter(p => p);
}
document.querySelector('#submit').addEventListener('click', function () {
// show activity
var loader = document.querySelector('#loader');
if (loader) loader.classList.add('show');
// get result
var inputElement = document.querySelector('#input');
var result = getPrimeNumbers(inputElement.value);
// append result
var outputElement = document.querySelector('#output');
if (outputElement) {
outputElement.innerText = result
}
// hide activity
if (loader) loader.classList.remove('show');
});
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment