Textbook Programming Project #1, page 905: Submit PrimeQueue.java Read descripti

Question

Textbook Programming Project #1, page 905: Submit PrimeQueue.java

Read description in the text, and study the pseudo-code provided (also on Wikipedia (Links to an external site.)). Then create a class named PrimeQueue.java that contains a public static method getPrimes(n), which returns a Queue of prime numbers up to n. I will test these programs with a simple test like:

Queue<Integer> q = PrimeQueue.getPrimes(12345);

Please remove (or comment out) your System.out calls, as my testing will be external. Also be aware of the Big-O of your algorithm, as nesting loops too deep here will really slow down the algorithm and be very apparent upon testing. Above example finds 1474 prime numbers and runs fast no matter how it's coded. Bump that up to getPrimes(12345678) so there are 800k+ primes and it still should be able to find that in a couple seconds.

NOTE: The pseudo code in text indicates two Queues (numbers and result). If you use an array like a Queue for the numbers start, and kind of follow the Wikipedia example, and build the Queue on the final step, then the total process time can be much faster.

Explanation / Answer

import java.util.LinkedList;
/**
* @author Srinivas Palli
*
*/
import java.util.Queue;

public class PrimeQueue {

   /**
   * method to get the primes in the Queue<Integer>
   *
   * @param number
   * @return
   */
   public static Queue<Integer> getPrimes(int n) {

       // Create array of booleans
       Boolean[] prime = new Boolean[n];

       // Make each element in isPrime true to start with
       for (int i = 1; i < n; i++) {
           prime[i] = true;
       }

       // Start from 2 and check for primes
       for (long i = 2; i <= n; i++) {
           // Change int to long due to ArrayIndexOutOfBoundsException

           // If true...
           // (type cast i from long to int to work)
           if (prime[(int) i - 1]) {

               // See if next numbers are primes
               for (long j = (i * i); j <= n; j += i) {
                   prime[(int) j - 1] = false;
               }

           }
       }

       // Create and build primes queue
       Queue<Integer> primes = new LinkedList<Integer>();
       for (int i = 1; i < n; i++) {
           if (prime[i]) {
               primes.add(i + 1);
           }
       }

       return primes;

   }

   /**
   * @param args
   */
   public static void main(String[] args) {

       Queue<Integer> primes1 = PrimeQueue.getPrimes(12345);
       System.out.println("No of Primes for n is 12345:" + primes1.size());

       Queue<Integer> primes2 = PrimeQueue.getPrimes(12345678);
       System.out.println("No of Primes forn n is 12345678 :" + primes2.size());

   }
}

OUTPUT:
No of Primes for n is 12345:1474
No of Primes forn n is 12345678 :809227

Note:
if n is 12345678 it takes 3 seconds , if you dont want the test just comment the
main method

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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