title: Java Complexity Class for this Program?
body: <p>for this assignment, I have to create a program that finds and returns a queue of all prime numbers up to integer n using the Sieve of Eratosthenes. While I got it to work, I am still pondering about the big O for my code. It seems like I've nested too many loops into it making it run too slow when calculating very large numbers. For instance, calculating:</p>
  
  <pre><code>Queue&lt;Integer&gt; q = PrimeQueue.getPrimes(1234567);
  </code></pre>
  
  <p>Takes nearly three minutes! What I'm asking is: Is such a long run-time expected for a task such as this? Is there is a more process-friendly way to do this within the confines of this assignemnt(While still using two queues and returning one of them)? What is the complexity class of this program? Thanks!</p>
  
  <p>Here's my code:</p>
  
  <pre><code>public static Queue&lt;Integer&gt; getPrimes(int n) {
      if (n &lt; 2) { // If illegal argument
          throw new IllegalArgumentException("n can't be less than 2.");
      }
      Queue&lt;Integer&gt; numbers = new LinkedList&lt;Integer&gt;();
      Queue&lt;Integer&gt; primes = new LinkedList&lt;Integer&gt;();
  
      // fills queue w/ numbers from 2 to n inclusive // throw exception if n &lt; 2
      for (int i = 2; i &lt;= n; i++) {
          numbers.add(i);
      }
  
      do { // do while b/c it will always execute once
          int prime = numbers.remove(); // gets first prime number from first value of numbers
          primes.add(prime); // adds to the prime 
          int numbersSize = numbers.size(); // used to keep track when looping over the numbers queue
          for (int i = 0; i &lt; numbersSize; i++) { // goes through each number to elim multiples of prime
              int numTemp = numbers.remove(); // will add to back of numbers if not divisible by prime (otherwise deleted)
              if (numTemp % prime != 0) {
                  numbers.add(numTemp); // put back into back of queue
              }
          }
      } while (!numbers.isEmpty()); // Keeps running as long as there is a value in numbers
      return primes;
  }
  </code></pre>