MOD 5 - QUEUE - VERSION 2

by SHELDON PASCIAK

HTML

<!--

    MODULE 5 - program 1 - version 2 - sheldon pasciak

    uses a queue to implment a search for prime numbers
    using "the sieve of Eratosthenes".

-->

Find Prime Numbers from [2..
<input type="number" value="10" min=2 id="userNumber" /><br />
<input type="button" value="Click to find primes" id="findPrimes" /><br />

<div id="output"></div>

<!--


Assignment 1 -
 
You are going to create a List. You will then fill it with numbers consecutively numbered from 2 to n where n is entered by the user.
 
Create a second List - this one should be a Queue - it is empty.
 
Once you have the first List filled we are going to use a technique called Sieve of Eratosthenes which uses first queue to fill the second queue. You will need to look at the algorithm for this https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 
 
Here is the simple method to do this - L1 is the first list, Q1 is the Queue.
 
1. Go to 1st element in L1 (which will be 2).
2. Because it exists - Push this into Q1 and remove it from L1
3. Iterate through each element of L1 and if the value is divisible by 2 remove it.
4. When done go back to the beginning of the list (the value will be 3 the second time around)
5. Print Iteration 1, Value of L1 (all elements) and Q1 (all elements)
6. Repeat steps 2-5 with this new element - repeat until L1 is empty.
 
Sample output with input 10
 
Iteration 0:  L1 = 2 3 4 5 6 7 8 9 10, Q1 = ,
Iteration 1:  L1 = 3 5 7 9, Q1 = 2
Iteration 2: L1 = 5 7, Q1 = 2 3
Iteration 3: L1 = 7, Q1 = 2 3 5
Iteration 4: L1 = , Q1 = 2 3 5 7

-->

CSS

* {
    
    font: 12pt courier;

}

JavaScript

// Module 5 - program 1 - version 2 - SHELDON PASCIAK

var myQueue = function () {
    this.first = null;
    this.size = 0;
}

var Node = function (data) {
    this.data=data;
    this.next=null;
}

myQueue.prototype.asString = function () {
    var strOutput = "";
    if (this.first==null) {
        return "";
    } else {
        current=this.first;
        strOutput += current.data + " ";
        while (current.next) {            
            current = current.next;   
            strOutput += current.data + " ";
        }        
    }      
    return strOutput;
}

//moves to the end at each enqueue
myQueue.prototype.enqueue = function (data) {

    var node = new Node(data);
    var current = null;

    if (this.first==null) {
        this.first=node;
    } else {
        current=this.first;
        while (current.next) {
            current = current.next;   
        }
        current.next = node;
    }    

    this.size++;
    return node; //return new object
}

//pops off first element in linked list returns it
myQueue.prototype.dequeue = function() {
    var temp = this.first;
    this.first = this.first.next;
    this.size--;
    return temp;
}

// returns true if size is 0
myQueue.prototype.isEmpty = function () {
    return ( this.size === 0 )
}

// finds primes from 2...userNumber using sieve of Eratosthenes
function findPrimes(maxNumber) {

    var theOutput = "";
    var iterations = 0;
    var primeFactor = 2;
    var mathInput = 0; // holds dequeue'd value as lists are used
    var L1 = new myQueue(); // numbers to filter using sieve
    var Q1 = new myQueue(); // list of primes
    var saveList = new myQueue(); // non divisors of current Prime for use in next iteration

    //add numbers to L1 from 2 up to userNumber
    for (var i=2;i<=maxNumber;i++){

        /* 
        each call to enqueue does 1...n steps to end of 
        current link list in order to modify node.next 
        to the new node added
        */

        L1.enqueue(i); 

...