Create a class named PrimeQueue.java that contains a public static method getPri

Question

Create a class named PrimeQueue.java that contains a public static method getPrimes(n), which returns a Queue of prime numbers up to n.

Test code will be: Queue<Integer> q = PrimeQueue.getPrimes(12345);

1. Write a Primes program that finds prime numbers using the Sieve of Eratosthenes, an algorithm devised by a Greek mathematician of the same name who lived in the third century BC. The algorithm finds all prime numbers up to some maximum value n, as described by the following pseudocode: create a queue of numbers to process. fill the queue with the integers 2 through n inclusive. create an empty result queue to store primes. repeat the following steps: obtain the next prime p by removing the first value from the queue of numbers. put p into the result queue of primes loop through the queue of numbers eliminating all numbers that are divisible by p. while (p is less than the square root of n). all remaining values in the numbers queue are prime, so transfer them to the result primes queue Wikipedia has a nice description and animation of this algorithm in action: http:/len.wikipedia.org/wiki/Sieve_of_Eratosthenes

Explanation / Answer

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PrimeQueue
{
   public static Queue<Integer> getPrimes(int n)
   {
       int p;
       // create a queue of numbers to process
       Queue<Integer> numbers = new PriorityQueue<Integer>();
       // fill the queue with the integers 2 through n inclusive
       for(int i = 2; i <= n; i++)
       {
           numbers.add(i);
       }
       // create an empty result queue to store primes
       Queue<Integer> result = new PriorityQueue<Integer>();
      
       do{
           // obtaining next prime p by removing the first value from the queue of numbers
          p = numbers.poll();
           // put p into the result queue of primes.
          result.add(p);
           // iterator to loop through queue of numbers
          Iterator<Integer> itr = numbers.iterator();
           while(itr.hasNext())
           {
              // eliminating all numbers that are divisible by p
              if(itr.next() % p == 0)
               {
                   itr.remove();
               }
           }
       }while(p < Math.sqrt(n));
       // all remaining values in numbers queue are prime, so transfer then to the result primes queue.
       result.addAll(numbers);
      
       return result;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.