# Assignment 4: Arrays, Primes, and a Sieve

## More Text Field I/O on the Web Page

• Like we did in Assignment 3, we are going to use text fields on the HTML page for input to the program, and to receive the output returned by the program.

• Your main JavaScript function will be called -- as we have always done -- by clicking a button on the web page.

• The information in the input text box(es) on the web page will be sent to your JavaScript program as arguments to the main function.

• You will communicate back results from your main function by the "return" statement; whatever you return will be put into the output text field on the web page by the HTML code I have provided.

• In addition to the main function (which I have named "myMain") you will be writing two more functions (or more if you wish to write more). One suggestion is to write data validation functions so that your main function code is uncluttered and easier to read. Another suggestion is the Sieve itself can be made a function. Also, you could write a "findKthBack" function when the Sieve array has been constructed. Your choice.

• Inputs: the user will send in an integer (upperLimit) and another integer (kthBack). See the data validations section for valid ranges.

• Output: the main function "myMain" will return an integer greater than 1 if there are no problems, or an error message (string) if there are problems.

## Overall program description

It might make more sense to read the description of the program functionality while viewing the HTML template I have prepared for you to use on this program.

You are to write a JavaScript program that computes all the prime numbers from 1 up to some upper limit. It then returns 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 computers 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 return 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 return 31. Note that if the upper limit is itself prime (like 47) then the upper limit counts as the 1st back.

## 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:
• upperLimit: this should be an integer greater than or equal to 2 (because 0 and 1 are not prime); other input forms should be rejected, including non-numbers, non-integers, and values below 2.

• kthBack: this should also be an integer, it must be larger than 0, and it must be smaller than upperLimit. Other forms should be rejected, including non-numbers, non-integers, and values less than 1.
Note that when invalid input is detected, the myMain function should return an appropriate error message (string) like you did in Assignment 3.

## 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 returns 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 return that one. Remember that if upperLimit itself is prime, the it counts as the "1th back".

## Examples (Test Data)

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.

2281
 upperLimit kthBack return 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.

## Hints

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.