Sieve of Eratosthenes Primes Efficiency

Question

I'm fairly new to Java and was trying to make a program that's generates the primes from 2 - 100. I originally had a design of my own making but it was fairly inefficient so I did some research and come across the Sieve of Eratosthenes, which is supposedly the the efficient way to find primes from 2 - n.

public class SieveofEratosthenes {
    public static int[] primes(int num) {
        int primeCounter = 0;
        int[] numPrimes;
        // Boolean array made 1 element longer because SOE starts at 2
        // i.e. index 2 will correspond to 2, instead of index 0 corresponding to 2 (0, 1 will be unused)
        boolean[] primes = new boolean[num + 1];
        // Fill primes array with true
        for (int i = 2; i < primes.length; i++) {
            primes[i] = true;
        }

        /* 
         * Calculate primes up to num using Sieve of Eratosthenes algorithm
         */
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (primes[i]) {
                for (int k = i * i; k <= num; k += i) {
                    if (primes[k]) {
                        primes[k] = false;
                        primeCounter++;
                    }
                }
            }
        }

        /*
         *  Return array
         */
        numPrimes = new int[(num - 1)- primeCounter];  // Set size equal to number of primes in primes
        primeCounter = 0; // Reuse variable
        for (int i = 2; i < primes.length; i++) {
            if (primes[i]) {
                numPrimes[primeCounter] = i;
                primeCounter++;
            }
        }
        return numPrimes;
    }// End primes()
}// End class

I don't think I have a complete grasp on the concept of the Sieve of Eratosthenes algorithm, but I'm pretty sure I've got most of the key points.

How efficient is my code? Are there any particularly popular ways of implementing the Sieve of Eratosthenes into Java?

Answer 1

Your code is mostly right. primeCounter is a misleadingly named variable, since it counts non-primes. And, similarly, primes isn't an array of primes, but rather an array of flags indicating prime-ness. It would be better to name this one isPrime.

There is an Arrays.fill method that you may want to use for clarity:

Arrays.fill(isPrime, true);

And it may be easier to simply add the primes as you go though, and return an ArrayList<int>:

/* 
 * Calculate primes up to num using Sieve of Eratosthenes algorithm
 */
ArrayList<int> primes = new ArrayList<int>();
for (int i = 2; i <= num; i++) {
    if (isPrime[i]) {
        primes.add(i);
        for (int k = i * i; k <= num; k += i) {
            isPrime[k] = false;
        }
    }
}
return primes;

The other advantage of ArrayList is that you don't have to have a separate index to keep track of where in your array you're inserting into - let the container do its job!