You are going to create a Queue alternately you can create a

You are going to create a Queue. (alternately you can create a list and simply implement enqueue and dequeue functions in the List - that will technically make it a queue). You will fill the first list with numbers consecutively numbered from 2 to n where n is entered by the user (we will call this Q1). When creating your Queue object use the correct function names for enqueue and dequeue functions. Again - sorry, cannot use an Javascript array in your implementation - you need to implement enqueue and dequeue.

Create a second empty Queue Q2.

Once you have the first Queue 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 algorithm;

1. Dequeue 1st element in Q1 (which will be 2). You will need to remember the value of this element - we will call it X.

2. Enqueue this element into Q2 (Q2 is the list of primes)

3. Iterate and Dequeue each successive element of Q1

     If the value is divisible by X, go to the next element

     if the value is not divisible by X enqueue back onto Q1, go to the next element.

4. Print the values of Q1 and Q2 after each time through.

5. When done go back to the beginning of the Q1 and repeat steps 1-3 (the first value will be 3 the second time around)

Sample output with input 10

Iteration 0: Q1 = 2 3 4 5 6 7 8 9 10, Q2 = ,

Iteration 1: Q1 = 3 5 7 9, Q2 = 2

Iteration 2: Q1 = 5 7, Q2 = 2 3

Iteration 3: Q1 = 7, Q2 = 2 3 5

Iteration 4: Q1 = , Q2 = 2 3 5 7

Solution

import java.util.*;

public class SieveMain {

public static void main(String[] args) {

System.out.println();

Scanner console = new Scanner(System.in);

Sieve s = new Sieve();

for(;;) {

System.out.print(\"Maximum n to compute (0 to quit)? \");

int max = console.nextInt();

if (max == 0)

break;

System.out.println();

s.computeTo(max);

s.reportResults();

System.out.println();

}

}

}

public class Sieve {

private Queue<Integer> primes;

private Queue<Integer> numList;

private boolean computed = false;

private int max;

private int count = 0;

// constructs a sieve object

Sieve(){   

primes = new LinkedQueue<Integer>();

numList = new LinkedQueue<Integer>();

}

void computeTo(int n){

max = n;

computed = true;   

if (n < 2){

throw new IllegalArgumentException (\"n must be greater than or equal to 2!\");

}

for (int i = 2; i <= n; i++ ){

numList.enqueue(i);

}

Queue<Integer> temp = new LinkedQueue<Integer>();

Integer num;

do {

num = numList.dequeue();

if (num != null){

primes.enqueue(num);

for (int i = 0; i < numList.size(); i++){

Integer num2 = numList.dequeue();

if (num2 % num != 0){

temp.enqueue(num2);

}

}

numList = temp;

}

} while (num < Math.sqrt(n));

}   

/**

* reports the primes to System.out

*/

void reportResults(){

if (!computed){

throw new IllegalStateException (\"No call has been made on the computeTo method!\");

}

System.out.println(\"Primes up to \" + max + \" are as follows:\");

System.out.println(primes);

}

/**

*

* @return max - the value of n that was used last time computeTo was called

*/

int getMax(){

if (!computed){

throw new IllegalStateException (\"No call has been made on the computeTo method!\");

}   

return max;

}

}

public interface Queue<E> {

// post: given value inserted at the end of the queue

public void enqueue(E value);

// pre : !isEmpty()

// post: removes and returns the value at the front of the queue

public E dequeue();

// post: returns true if the queue is empty, false otherwise

public boolean isEmpty();

// post: returns the current number of elements in the queue

public int size();

}

import java.util.*;

public class LinkedQueue<E> implements Queue<E> {

private LinkedList<E> elements;

// post: constructs an empty queue

public LinkedQueue() {

elements = new LinkedList<E>();

}

// post: given value inserted at the end of the queue

public void enqueue(E value) {

elements.addLast(value);

}

// pre : !isEmpty()

// post: removes and returns the value at the front of the queue

public E dequeue() {

if (isEmpty())

throw new IllegalStateException(\"attempt to dequeue empty queue\");

return elements.removeFirst();

}

// post: returns true if the queue is empty, false otherwise

public boolean isEmpty() {

return elements.isEmpty();

}

// post: returns the current number of elements in the queue

public int size() {

return elements.size();

}

// post: returns a String representation of the queue contents

public String toString() {

return \"front \" + elements + \" back\";

}

}