Assignment 3: Arrays, Primes, and a Sieve

• Structure your program as a "main" JavaScript function named "myMain" with no arguments, and put in a single call to myMain to get it all going. The function myMain will return null. All user input will be done with prompt statements; all your output will be done via alert statements.

• In addition to the myMain function 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. It is your choice.

• Remember that arrays can be passed as arguments to functions just like simple variables and constants can.

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

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

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.

• Try computing a sieve with some big upper limit, like say 10,000,000. Now you can ask the user (in a loop) to give an integer and you can quickly say if that integer is a prime or not. This is called primality testing and is important in cryptography. The sieve is very efficient to compute. The drawback is that any specific instance has as upper limit; if you want to know the primality of 10,000,001, then you will have to rebuild the sieve with a larger upper limit. Another drawback is that the cost (tradeoff) for compute time efficiency is that it uses a large amount of space: the boolean array.

• You can use the Sieve as a way of printing all primes from 1 up to the limit. Simply print out a number when you are building the Sieve and discover a "true" in the array. You can also build the Sieve, then go back through it and print the "true" numbers, but this approach traverses the array twice. The drawback to this is the upper limit; you cannot use the Sieve to print all primes (well, there are an infinite number of primes anyway), only those from 1 to some limit.

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.
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.

2281
 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.

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.