Sieve of Eratosthenes in JavaScript

Question

newbieJS 0 Newbie Poster

13 Years Ago

I should probably begin by stating that I am not a mathematician, not even close. When asked to produce a JavaScript program using the Sieve of Eratosthenes, I started googling. There are a lot of examples out there but very few are for JavaScript, and even fewer include comments.

Could someone help me to understand how to produce a list of the prime numbers between 1 and 100 using the Sieve of Eratosthenes and arrays in JavaScript? I can think of a few very complicated ways of doing this, but I'm hopeful that your expertise will teach me the better, faster, and smarter way.

With thanks! Lots and lots of thanks!

javascript

2 Contributors
6 Replies
2K Views
1 Day Discussion Span
Latest Post 13 Years Ago Latest Post by newbieJS

Airshow 416 WiFi Lounge Lizard

13 Years Ago

nJS,

What an interesting problem.

My solution is about as efficient as I can make it. The sieve function is 9 (well packed) lines of code, including its function wrapper. Everything else is user interface or comments.

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head>
<title>Airshow :: Sieve of Eratosthenes</title>
<style type="text/css">
* {
	color: #fff;
}
body {
	background-color: #006699;
}
input { color: #000; }
input#N { text-align: center; }
#primes {
	padding: 10px;
	background-color: #0099CC;
	border: 1px solid #003366;
}
</style>

<script>
//N is the number up to (and including) which we find primes.
//n is an incremental counter, starting at 2, ending at N/2 (no point going beyond half N)
//p is a "runing product", starting at 2n each time through the inner loop
//primes is an array initialised to 'undefined's (not integers!). Non-primes are set to true as they are discovered.
//str is an array in which we build the output string.
function sieve(N){
	var n, p, primes=[], str=[];
	for(n=2; n<N/2; n++){
		if(primes[n]) { continue; } //Only address numbers not already eliminated (and their multiples)
		for(p=2*n; p<=N; p+=n){ primes[p]=true; }//eliminate all multiples of n
	}
	for(n=2; n<=N; n++){ if(!primes[n]) str.push(n); }//build the resulting string of primes, starting at 2
	return str.join(', ');
}

onload = function() {
	var N = document.getElementById('N');
	var go = document.getElementById('go');
	var container = document.getElementById('primes');
	go.onclick = function(){
		container.innerHTML = "working ...";
		setTimeout(function(){container.innerHTML = sieve(N.value);}, 10);
	}
};
</script>
</head>

<body>

<h1>Sieve of Eratosthenes</h1>
<input id="N" type="text" size="6" value="100" />&nbsp;<input id="go" type="button" value="Go" />
<div id="primes"></div>

</body>
</html>

For efficiency, the secret is to use an array initialised to "undefined" and set to true for each non-prime as it is discovered. An earlier attempt used false/true but that required an extra line to initialise the array.

Initial temptation is to use an array of integers, which would be horribly inefficient in terms of memory and lines of code.

Airshow

Edited 13 Years Ago by Airshow because: n/a

Airshow 416 WiFi Lounge Lizard

13 Years Ago

nJS,

It's good that you are working at it and not just accepting what other people have done.

Your code and mine are very similar with a small but significant difference. Whereas you initialise your numbers array to true all through, I start with an uninitialized primes=[] , then selectively set array elements to true to indicate the primes as they are discovered.

This has two big advantages (especially when N is large). Firstly, there's no need for the initialisation loop, where you set N array elements to true. Secondly, the resulting array contains only elements for the primes - all the non-primes are not represented. Javascript makes this possible by implementing "sparse arrays", by which an array with non-consecutive indexes has no "gaps" - elements exist only for those indexes that are set. All others remain "undefined", as when the array was created.

Another difference is the way we build our output strings. String += String; should be avoided at all costs - not just here but in all javascript programming. The reason is that the original string is discarded and a new string created. It is strongly recommended to build strings in an array, adding new bits with Array.push(String). When all bits have been added just put them together with Array.join(glue), where glue is a string to be inserted between each adjacent pair of elements in the Array. And there's no need to strip anything off either end.

1. What does the var "htmlStr = '';" do?

This simply creates an empty string with the vaiable name htmlStr . Further down the code, the line htmlStr += ', ' + i; builds htmlStr one prime number at a time with ', ' as a separator. (This string building method is what you should avoid as I explain above).

Airshow

Edited 13 Years Ago by Airshow because: n/a

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

newbieJS 0 Newbie Poster · Answer 1 · 2011-02-01T08:18:43+00:00

I will test your code this evening, I just wanted to thank you again for taking the time to respond.

I had, as you say, a horribly inefficient version - hehe. I'm always glad to clean it up.

newbieJS 0 Newbie Poster · Answer 2 · 2011-02-01T10:27:01+00:00

This is the fourth program I have ever written, so I'm having trouble trying to update my code to include some of yours. I'm so new at this that it seems the more edits I make the more mistakes I include.

I don't want to make this too flashy, although I like the input button and the style applied, I'm far more interested in wrapping my head around the JavaScript. It can be frustrating at times:(

Would you mind helping me one more time? It is a lot to ask, but I find that I am learning a lot more from the discussions on this forum than anywhere else.

Here goes, my instructions are to:
1. Create an array with all elements initialized to 1 (true), prime subscripts within the array will remain true (1) all other numbers will be set to false (0)

2. Starting with array subscript 2 (subscript 1 must be prime), every time an array element is found whose value is 1, loop through the remainder of the array and set to zero every element whose subscript is a multiple of the subscript for the element with value 1. For array subscript 2, all elements beyond 2 in the array that are multiples of 2 will be set to zero (subscripts 4, 6, 8, 10, etc.); for array subscript 3, all elements beyond 3 in the array that are multiples of 3 will be set to zero (subscripts 6, 9, 12, 15, etc.); and so on.

When this process is complete, the array elements that are still set to 1 indicate that the subscript is a prime number

I honestly have tried this and the best I can get is an alert that my prime numbers are not defined. I think the wording has confused me and when I compare the question to the thousands of examples on the web, including your great example Airshow, none seem to use this technique.

Can you tell I'm a wee bit frustrated? I'm being asked to program things that I've never been introduced to, that said I'll keep at it - there is always an answer, sometimes it just a little harder to find :)

BTW: I quite like your comment about how interesting the question was for you, makes me think of the silver lining.

newbieJS 0 Newbie Poster · Answer 3 · 2011-02-01T15:42:51+00:00

I have solved most of my problems, using helpful hints from a lot of experienced programmers. The below example is working, and I only have a few questions:

1. What does the var "htmlStr = '';" do?
Am I correct to assume that all it does is add a space in between each listed result. If so, could I not clean up the code to eliminate it and insert a space manually like in a document.write statement? Not sure, I was never doing this before.

Take a look :)

<body>
<div id="primeResults"></div>

<script type="text/javascript">
// set up array , storing 1000 numbers
var numbers = [],
  numbersSize = 1000,

  results = document.getElementById('primeResults'),  // store the resuls in the div with the same id. 
 
  htmlStr = '';  // this var will insert a space between the listed results ?


// Create an array with all elements initialized to 1 (true).
for (var i = 0; i < numbersSize; i++) {
  numbers[i] = 1;
}
// Iterate through the array starting with array subscript 2
for (i = 2; i < numbersSize; i++) {
  // every time an array element is found whose value is 1
  if (numbers[i] == 1) {
    // set to zero every element whose subscript is a multiple
    for (j = 2; i * j < numbersSize; j++) {
      numbers[i * j] = 0;
    }
  }
}
// the array elements that are still set to 1 indicate that the subscript is a prime
//  These subscripts can then be printed.
// print the prime numbers between 1 and 999. Ignore element 0 of the array.
for (i = 1; i < numbersSize; i++) {
  
  // Note, 1 is not actually a prime number, so this should really start with i = 2 instead. 
  // Leaving it incorrect as per the directions.
  if (numbers[i] == 1) {
    htmlStr += ', ' + i;
  }
}
// Strip off the first ', ' from the htmlStr (why?)
if (htmlStr.length > 2) {
  htmlStr = htmlStr.substr(2);
}

// Print the results
results.innerHTML = htmlStr;

</script>

</body>

newbieJS 0 Newbie Poster · Answer 4 · 2011-02-02T05:06:18+00:00

I'll give it a try. Thanks for your detailed explanation - you must be a teacher? If not, don't be offended, be inspired it is certainly a possibility for you (should you be interested)

Thanks again