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 29Then, 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 47The 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.
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.
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".
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 | 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 | 2281
| 7500 | 50 | 7001 |
| 7500 | 301 | 4831 |
| 10 | 9 | error |
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.