# JavaScript Homework Help - Sieve of Eratosthenes

I’m having a bit of trouble understanding the instructions for one of my assignments in my JavaScript class. Maybe it’s just me, but I feel like the instructions aren’t very clear; I get to like step 2 and I’m not sure what to do from there. Is there anyone here who understands this and could help me out? Any help would be much appreciated. Thanks.

1. Prime numbers can be generated by an algorithm known as the Sieve of Eratosthenes. The algorithm for
this procedure is presented here. Write a program called primes.js that implements this algorithm. Have the
program find and display all the prime numbers up to n = 150.

Sieve of Eratosthenes Algorithm

To Display All Prime Numbers Between 1 and n

Step 1: We need to start with all the numbers representing the range of numbers that are possible
candidate primes. So, create an array of consecutive integers from 2 to n: (2,3,4,…n). I wouldn’t hand-code
this. I would use a loop to populate the array.

Step 2: At each step we select the smallest number and remove all it’s multiples. So we’ll start with an outer
loop that goes from 2 to n. initially, let p equal 2, the first prime number.

Step 3: In an inner loop we need to iterate over all the numbers that are multiples of p, i.e for 2, that’s 2,4,6,8
etc. Each time, setting it’s value to false in the original array.

Step 4: Find the first number greater than p in the list that is not marked False. If there was no such number,
stop. Otherwise, let p now equal this number( which is the next prime), and repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked False are prime.

That isn’t how I would approach it. I think it would be more efficient to use “remainder” (aka modulus) and “filter” to reduce the array size each loop.

But because this is an assignment I guess it’s best to code it up in compliance with the way it wants the loops to be.

At least filtering out known False should improve performance some.

Have you figured out a rough alpha version of the loop logic you’ll need?

Is it the explanation of what the Sieve of Eratosthenes is that is not clear? If you write down all the numbers from 1 to 100. then start with the lowest prime number, 2. Cross off all multiples of 2 in the list (ie 4, 6, 8, 10, …). Then the next number not crossed off (the 3) will be a prime so go ahead and cross off all the multiples of 3, unless they are already crossed off (so 9, 15, 21, …). The next low number not crossed off will be the 5 so do the same for that one. Continue that way until all multiples of primes are crossed off. The numbers left that are not crossed off are prime numbers.

Now write the code for this where crossing off a number is just like calling the value false.

There are other ways of finding prime numbers, but it looks like you are required to use the Sieve of Eratosthenes in your assignment.

1 Like

Ok, I think I got it figured out.

The way Step 2 begins with “At each step” had me thinking I was supposed to create an inner loop to remove multiples inside the loop from Step 1, which doesn’t make much sense. I think I just needed to take a break and go back and look at it again.

This is what I came up with:

``````//Define number limit
var n = 150;

//Create and populate number array
var numbers = [];
for (var i = 0; i <= n; i++) {
numbers.push(true);
}

//Remove multiples of prime numbers
for (var i = 2; i <= n; i++) {
for (var j = i * i; j <= n; j += i) {
numbers[j] = false;
}
}

//Create and populate array of prime numbers
var primes = [];
for (var i = 2; i <= n; i++) {
if (numbers[i]) {
primes.push(i);
}
}

//Output prime number array
console.log(primes);
``````

I’m sure it’s not perfect, but it seems to work.

2 Likes

I know the requirement is “n = 150” but I think during development it might be easier to see what the results are (and safer) starting lower and working your way up to 150.

eg. n = 25 would be enough for a start, if all looks good, n = 50, etc. until you get to n = 150

That way there would be less results to evaluate and less danger of a bad loop causing memory or timeout problems.

1 Like

Though to be pedantic, the Sieve isnt a method of generating prime numbers, it’s a method of eliminating compound numbers.

There is a break-even point at which the Seive actually takes longer than an elimination-checking method like @Mittineague described (and which would be recommended).

Additionally, step 3 is wrong in your assignment descriptor. You start at 2p, not p.

For 2, the list to set to false should start at 4, not 2. 2 is prime, why would you eliminate it?!?!

Also, strictly speaking you’ve cheated and used an acceleration of the actual sieve by starting your remove-inner loop at i^2 instead of 2*i. It works, but it’s not the assignment…

This topic was automatically closed 91 days after the last reply. New replies are no longer allowed.