Simple implementation of the Sieve of Eratosthenes to find prime numbers.
-
-
Save gomfunkel/3842396 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes
Simple implementation of the Sieve of Eratosthenes to find prime numbers.
This file contains hidden or 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
| function( | |
| a, // Check for primes in the range from 1 to 'a' | |
| b, // Array holding numbers as key and primeness as value | |
| c, // Placeholder | |
| d // Placeholder | |
| ){ | |
| b=[]; // Initialize array | |
| for(c=1;c<a;b[++c]=1); // Initialize with all numbers being 1 (prime) | |
| for(c=2;c<=Math.sqrt(a);c++) // Loop through all numbers <= sqrt of the range to check | |
| for(d=c;b[c]&&d<=a-c;b[d+=c]=0); // Delete all multiples of the current number as these can't be prime | |
| // Only consider numbers marked as prime (b[c]&&) | |
| return b // Return the sieved array | |
| } |
This file contains hidden or 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
| function(a,b,c,d){b=[];for(c=1;c<a;b[++c]=1);for(c=2;c<=Math.sqrt(a);c++)for(d=c;b[c]&&d<=a-c;b[d+=c]=0);return b} |
This file contains hidden or 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
| DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE | |
| Version 2, December 2004 | |
| Copyright (C) 2011 YOUR_NAME_HERE <YOUR_URL_HERE> | |
| Everyone is permitted to copy and distribute verbatim or modified | |
| copies of this license document, and changing it is allowed as long | |
| as the name is changed. | |
| DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE | |
| TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION | |
| 0. You just DO WHAT THE FUCK YOU WANT TO. |
This file contains hidden or 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
| { | |
| "name": "sieveOfEratosthenes", | |
| "description": "Simple implementation of the Sieve of Eratosthenes to find prime numbers.", | |
| "keywords": [ | |
| "prime", | |
| "number", | |
| "math" | |
| ] | |
| } |
This file contains hidden or 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
| <!DOCTYPE html> | |
| <title>Sieve of Eratosthenes</title> | |
| <div>Expected value (Primes between 1 and 100): <b>2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97</b></div> | |
| <div>Actual value (Primes between 1 and 100): <b id="result"></b></div> | |
| <script> | |
| var sieveOfEratosthenes = function(a,b,c,d){b=[];for(c=1;c<a;b[++c]=1);for(c=2;c<=Math.sqrt(a);c++)for(d=c;b[c]&&d<=a-c;b[d+=c]=0);return b} | |
| var sieved = sieveOfEratosthenes(100); | |
| var result = ""; | |
| for (i = 1; i <= 100; i++) | |
| if (sieved[i]) | |
| result += i+', '; | |
| document.getElementById("result").innerHTML = result.substring(0, result.length-2); | |
| </script> |
Hmm, actually it isn't even necessary to floor the sqrt...
Instead of if, you can put the testing of b[c] inside the last for loop, saving 2 bytes:
function(a,b,c,d){b=[];for(c=1;c<a;b[++c]=1);for(c=2;c<=Math.sqrt(a);c++)for(d=c;b[c]&&d<=a-c;b[d+=c]=0);return b}
@atk Nice, thanks!
You're welcome, @gomfunkel
subscript.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Saved some bytes by flooring the sqrt using "0|" instead of ceiling it with "Math.ceil()" which is not necessary. Additionally sped up the sieving by only considering numbers still marked as prime when eliminating multiples.