Optimization of a "Sieve of Eratosthenes" in Java I have created a simple Pseudo "Sieve of Eratosthenes," for a class in Java. I am looking for the most optimized option, or at least an option that is more optimized than current. If there is any other advice that you have to offer, I would be more than happy to hear that as well.

import java.util.*;

public class SieveOfErantosthenes {

    public static void main(String[] args) {
        int testerIndex = 0, numbersOnLine = 0;
        Vector&lt;Integer&gt; primes = new Vector&lt;Integer&gt;(1, 1);
        for (int i = 0; i &lt; 1000; i++) {
            primes.add(i + 1);
        }
        primes.remove(0);
        while ((primes.get(testerIndex)) &lt; 500) {
            for (int i = testerIndex + 1; i &lt; 999; i++) {
                if (primes.get(i) % primes.get(testerIndex) == 0
                        &amp;&amp; primes.get(i) != 0) {
                    primes.set(i, 0);
                }

            }
            do {
                testerIndex++;
            } while (primes.get(testerIndex) == 0);
        }
        while (primes.contains(0)) {
            primes.remove((Integer) 0);
        }
        testerIndex = 0;
        while(testerIndex &lt; primes.size()){
            for(; numbersOnLine &lt; 15 &amp;&amp; testerIndex &lt; primes.size(); testerIndex++, numbersOnLine++){
                System.out.print(primes.get(testerIndex) + "\t");
            }
            System.out.println();
            numbersOnLine = 0;
        }
    }

}
Alright, a few notes:

Your for loop strikes one as odd.


 for (int i = 0; i &lt; 1000; i++) {
                primes.add(i + 1);
            }



Why not start iteration at 1 and have your conditional be  &lt;= 1000, and you could just call primes.add(i) Note that this is just an example to be equivalent to yours, just removing unnecessary bloat, it actually makes the most sense to start with 2 for a sieve, since it's the first prime. These changes would more clearly communicate your intention.

Courtesy of this answer I learned that a sieve is best implemented through a simple boolean array.


  boolean[] sieve = new boolean[1000];
    Arrays.fill(sieve, true);

 for (int prime = 2; prime &lt; sieve.length; prime++) {
        if (sieve[prime]) {
            // this is a prime number
          for (int notPrime = prime * 2; notPrime &lt; sieve.length; notPrime += prime) {
              sieve[notPrime] = false;
          }
        }
    }



As this answer notes there may be ways to improve it, but I like this implementation for being light on memory (booleans are 1 bit) and the performance and convenience of simply using the indexes as the prime or not prime values.

Edit: Although booleans actually take up 1 bit in memory, the actual number of bits allocated is JVM dependent and typically a byte is reserved for each boolean used. Although the performance would be intangible using a Bitset would be the target route to achieve 1 bit per boolean.

*If any of this was useful, please give the linked answer up-vote priority.