Assignment 3: Arrays, Primes, and a Sieve

Overall program description

You are to write a JavaScript program that computes all the prime numbers from 1 up to some upper limit. It then prints the kth prime number back from the upper limit. The user will input both the upper limit, and the kth back selection. The output is a single integer (or an error message).

An example right away will make this more clear. Let's call the two numbers given by the user "upperLimit" and "kthBack". Let's also say the user gives upperLimit as 30 and kthBack as 2. Then the program first computes all the primes from 1 to 30:

2  3  5  7  11  13  17  19  23  29
Then, the 2nd prime number back from 30 is 23. So the program would print 23.

Let's look at another example. The user gives upper limit of 47, and asks for the 5th back:

2  3  5  7  11  13  17  19  23  29  31  37  41  43  47
The 5th prime back from 47 is then 31, so the program would print 31. Note that if the upper limit is itself prime (like 47) then the upper limit counts as the 1st back.

Uses for the Sieve

Let's consider the example just given... upperLimit of 47. You are not computing the first 47 primes. You are instead creating a structure or mechanism that will tell if each integer between 1 and 47 is prime or not. Then you are counting backwards from 47 asking if each integer you get to is prime or not, and stopping after finding a certain number of primes (kthBack).

This means you can do several fun things (yes I am easily amused) with your sieve once the basic code is working correctly.

Input Data Validation

As in all your programs, you will need to validate the user's input data. For this exercise, the user is supplying two input values: Since we are doing an interactive program (meaning the user is typing input to the program while it runs) we can handle erroneous input two ways. When invalid input is detected, the myMain function can print "error" and quit. You can also write validation code that will notify the user that the input is bad and loop back to let the user try the input again.

The Basic Data Structure

We will create an array of boolean values (true, false). Let's call this array "prime". The idea is this: if prime[n] contains a true, then n is prime; if prime[n] contains a false, then n is not prime. While this bears some similarity to the function "isPrime" we used in Assignment 3, but is different in that when we fill in the proper booleans values for all the array slots we will have ALL primes in the range 2 to upperLimit.

Let's assume the user gives an upperLimit of 20 and kthBack of 3. The array "prime" of booleans will look like this when you have properly filled it with boolean values:

      F  F  T  T  F  T  F  T  F  F  F  T  F  T  F  F  F  T  F  T  F
prime __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __
      0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
Counting back from 20, we see the prime[20] if false so it is skipped, then prime[19] is true so there's the first back. Then prime[18] is false so it is skipped, and prime[17] is true so there's the 2nd back. Then prime[16] is false and skipped; prime[15] is false and skipped; prime[14] is false and skipped; finally, prime[13] is true so there is the 3rd prime back from 20. The program prints 13.

The Sieve: Finding the Primes

Now we need to get the array "prime" filled in with the correct booleans. One way to do this efficiently is to use the famous Sieve of Eratosthenes. This algorithm dates to the ancient Greeks.

We will first set all the values in the array "prime" to true The goal is to then go through the array and set the non-prime values to false. We start with setting prime[0] and prime[1] to false directly, as 0 and 1 are both not prime. Now we create a for loop running from 2 up to upperLimit. We examine prime[2] and find it "true"; this means 2 is prime. We then go through the rest of the array slots above 2 and set all multiples of 2 to false... we know if 2 is prime, then 4, 6, 8, 10, etc. are all not prime. Next we move from 2 to 3 and check prime[3]; we find a true, so 3 is prime. We then go through the array slots above 3 and set all multiples of 3 to false (not prime). And so on until we reach upperLimit. When we are done, all the array slots are set to true, or false correctly.

You may look up how the Sieve works online, but do not take code from online. Write your own solution. The algorithm is not lenghty to code up... but it will take some thinking to get all the array subscript expressions worked out.

Once the Sieve is filed in, we can then run a loop backwards, from upperLimit back towards 2. We count off prime numbers as we find them, and when we have counted "kthBack" of them we print that one. Remember that if upperLimit itself is prime, the it counts as the "1th back".

Examples (Test Data)

This oracle will show you how the program should work on various inputs.

Make sure your program properly detects and rejects all invalid inputs... like passing a non-number, or passing a negative number, or passing a non-integer.

upperLimit kthBack print value
14 1 13
30 2 23
47 5 31
47 1 47
20 3 13
175 10 127
1820 7 1759
1000 12 919
2287 1 2287
2287 2 2281
7500 50 7001
7500 301 4831
10 9 error

You can never be too thorough in testing. You can use a table of primes (google it) to create more test points on your own.


Grow your program a little piece at a time. Do not type in 100 lines of code and then hope it works. It won't... and then you won't be able to easily find the line(s) that are causing the problem(s).

Instead, build an outline of the algorithm with comments. Then go back and convert each comment into a few lines of code. Then test the few lines you added, see if the program is doing what you expect it to be doing.

For loops allow you to access the items in an array systematically... from index 0 on up in order. For the Sieve, you will have one main for loop that goes from 2 up to upperLimit; in this one you will be asking if prime[i] is true (meaning did we find a new prime number i). If it is true, then you will have an inner for loop completely inside the outer loop. The inner loop will use a different index variable (like k); k will start at i*2 and run up to upperLimit, and each iteration will increase k by i... meaning the inner loop is counting up by multiples of i.

When you write a new function, write a stub. This is a function that doesn't do anything much other than announce that it is working (via alert, for example). You might then make the stub alert its argument(s) so you can see that the correct information is being passed in.

You might also have the stub return a "fake value" of the correct type, range, and format so that the rest of the program that is calling it can use the stub. This means that if the function supposed to compute and return some non-negative number, then just put in "return 1" so that it at least appears to be working.

Once it is all connected up correctly and running when called, you can go back and make it produce the correct results and replace the "fake return" with the correct return value.