A Queue (specific type of Linked List). That is filled numbers consecutively num
ID: 3675451 • Letter: A
Question
A Queue (specific type of Linked List). That is filled numbers consecutively numbered from 2 to n where n is entered by the user. When creating the Queue object, it uses the correct function names for enqueue and dequeue. The second List - will be a Queue - it is empty. Once the first List is filled; A technique called Sieve of Eratosthenes will use the first queue to fill the second queue. The algorithm for this is here: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
A method of doing 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 - Enqueue this into Q1 and dequeue it from L1 3. Iterate through each element of L1 and if the value is divisible by 2 dequeue 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
Explanation / Answer
Sieve.java
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Sieve {
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter the number n for upper limit of queue entries");
int max=sc.nextInt();
Queue <Integer> primes; // Built in.
//List 1 for storing number from 2 to max
Queue<Integer> nums = new LinkedList<>(); //Use built in queue and LL
for (int i = 2; i <= max; i++)
{
nums.add(i);
}
primes = new LinkedList<>(); // Built in.
int p;
System.out.println("After iteration 0");
System.out.println("First queue");
Iterator<Integer> it=nums.iterator();
while(it.hasNext())
{
System.out.print(it.next()+" ");
}
System.out.println();
//keeping the count of iterations
int count=1;
do{
p = nums.remove();
it = nums.iterator();
//iterating over the queue 1
while(it.hasNext())
{
int i = it.next();
if (i % p == 0)
{
it.remove(); //removes the element if it is divisible by p
}
}
//adding the first element of the queue 1 which is a prime number to queue of primes
primes.add(p);
//printing the queue 1
System.out.println("After iteration "+count);
System.out.println("Queue 1");
it=nums.iterator();
while(it.hasNext())
{
System.out.print(it.next()+" ");
}
//printing the queue 2 i.e the one with the primes
System.out.println(" Primes");
it=primes.iterator();
while(it.hasNext())
{
System.out.print(it.next()+" ");
}
System.out.println();
count++;
} while (p < max && !nums.isEmpty());
}
}
sample output:
Enter the number n for upper limit of queue entries
25
After iteration 0
First queue
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
After iteration 1
Queue 1
3 5 7 9 11 13 15 17 19 21 23 25
Primes
2
After iteration 2
Queue 1
5 7 11 13 17 19 23 25
Primes
2 3
After iteration 3
Queue 1
7 11 13 17 19 23
Primes
2 3 5
After iteration 4
Queue 1
11 13 17 19 23
Primes
2 3 5 7
After iteration 5
Queue 1
13 17 19 23
Primes
2 3 5 7 11
After iteration 6
Queue 1
17 19 23
Primes
2 3 5 7 11 13
After iteration 7
Queue 1
19 23
Primes
2 3 5 7 11 13 17
After iteration 8
Queue 1
23
Primes
2 3 5 7 11 13 17 19
After iteration 9
Queue 1
Primes
2 3 5 7 11 13 17 19 23
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.