4
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ The understanding you need for the Sieve of Eratosthenes is fairly simple. A number is prime iff it is not divisible by any primes before it. So when we start from the smallest prime, 2, and mark all multiples of 2, then the next non-marked number in the list must be prime since it is not divisible by (i.e. not a multiple of) any primes before it. We can continue this method each time we find the next prime. One problem you are probably having is that you are starting with a somewhat optimized version of the algorithm (marking multiples of primes starting at i * i instead of 2 * i). \$\endgroup\$ – twohundredping Oct 21 '15 at 17:08
  • \$\begingroup\$ @twohundredping Thats not a problem, I did that for efficiency. In the algorithm it is unnecessary to start marking numbers composite on the first multiple of i (2 * i) because those should already be marked composite if you did it correctly. \$\endgroup\$ – RobertR Oct 21 '15 at 19:36
  • \$\begingroup\$ Yes this is true. I meant problem grasping the algorithm, not problem with the algorithm. I thought that skipping those smaller multiples may have been something you did not fully grasp. I always suggest starting your understanding of an algorithm at its most basic level and then optimizing from there if necessary. \$\endgroup\$ – twohundredping Oct 21 '15 at 21:24
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Alright thanks! I was avoiding using an ArrayList because I haven't learn't about them yet but I will switch some names around and use that Arrays.fill method; I didn't know there was support for that build into Java. \$\endgroup\$ – RobertR Oct 21 '15 at 16:32
  • \$\begingroup\$ @RobertR Yeah, Java has all sorts of goodies. Also, don't be to quick to accept answers here. Gotta give people time to write answers and such. \$\endgroup\$ – Barry Oct 21 '15 at 16:34
  • \$\begingroup\$ @juvian "greatly affects"? What? Once you pass the square root (which, btw, no need for Math.sqrt() anymore), the inner loop over k just doesn't do anything. That doesn't add to the runtime complexity. \$\endgroup\$ – Barry Oct 21 '15 at 17:11
  • \$\begingroup\$ @Barry my mistake, you are right, did not notice the i * i and thought it was i * 2 \$\endgroup\$ – juvian Oct 21 '15 at 17:15
  • \$\begingroup\$ @Barry Ah I see, the call to Math.sqrt() is pointless because i is getting squared anyway. Will make that change too. \$\endgroup\$ – RobertR Oct 21 '15 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.