5
\$\begingroup\$

I would like some feedback on a Java program which implements the Sieve of Eratosthenes to find prime numbers. Some of the 'features' I've included in the program include:

It uses a BitSet for identifying primes. What really gets checked is whether the index of any bit is prime. This eliminates the need to store the primes as actual numbers.

The program runs fairly quickly. It can identify over 105 million primes in about 44 seconds on my iMac.

I implemented a timer because I was tired of watching the clock.

I know I probably haven't done everything 'by the book' with this, so let me know where you think I need to do some cleanup.

//package Eratosthenes5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.BitSet;

public class Eratosthenes5 {

    // This uses a BitSet instead of a boolean array to see
    // if this saves any memory. It enables me to test approx.
    // 8x as many numbers. 109905151 is no longer my max.
    // The highest number I've reached, so far, is around 879,400,000.
    //
    // After giving more memory to the app, I can check for primes up
    // to around 2 billion. I've not determined the upper limit, but
    // I suspect it is the java max integer size. It finds almost
    // 100 million primes in under a minute.
    // 2^31 = 2,147,483,648

    /**
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        int maxSize = 1;
        int maxNumber;
        int maxSearch;
        int primeCount;
        int maxPrime;
        String name;
        name = getTheMaxNumber();
        while (name.compareTo("1") != 0) {
            long startTime = System.currentTimeMillis();
            maxSize = Integer.parseInt(name);
            maxNumber = maxSize + 1;
            maxSearch = (int) java.lang.Math.sqrt(maxNumber);
            primeCount = 1; // Start the count at 1 because 2 is prime and we'll
                            // start at 3
            maxPrime = -1;
            // use a BitSet array to maximize how many primes can be found
            BitSet numbList = new BitSet(maxNumber);

            numbList.set(0, maxNumber - 1, true); // set all bits to true

            numbList.clear(0);
            numbList.clear(1);

            // clear the even numbers (except 2, it's prime)
            for (long k = 4; k <= maxSize; k += 2) {
                numbList.clear((int) k);
            }

            // sieve out the non-primes
            for (int k = 3; k < maxSearch; k += 2) {
                if (numbList.get(k)) {
                    sieveTheRest(k, numbList, maxSize);
                }
            }

            // Count the primes
            for (int k = 3; k <= maxSize; k += 2) {
                if (numbList.get(k)) {
                    maxPrime = k;
                    primeCount += 1;
                    if (primeCount % 1000000 == 0) {
                        System.out.format("the "
                                + ((primeCount / 1000000 < 100) ? " " : "")
                                + ((primeCount / 1000000 < 10) ? " " : "")
                                + primeCount / 1000000
                                + " millionth prime is: %,11d%n", maxPrime);
                    }
                }
            }

            // we're done
            System.out.format("\nMy integer from beg: %,11d%n", Integer
                    .parseInt(name));
            System.out.format("array size         : %,11d%n", maxNumber);
            System.out.format("prime count        : %,11d%n", numbList
                    .cardinality());
            System.out.format("largest prime found: %,11d%n", maxPrime);
            System.out.format("max factor         : %,11d%n \n", maxSearch);

            long stopTime = System.currentTimeMillis();
            System.out.println("That took " + (stopTime - startTime) / 1000.0
                    + " seconds");

            name = getTheMaxNumber();
        }// end of while
        System.out.println("\nEnd of program");

    }// End of method Main
    /**
     * 
     * @return Passes back a string holding the maximum number to check
     */
    static String getTheMaxNumber() {
        BufferedReader dataIn = new BufferedReader(new InputStreamReader(
                System.in));
        String bigNumber = "";
        System.out.print("Please enter an integer value (1 to quit): ");
        try {
            bigNumber = dataIn.readLine();
        } catch (IOException e) {
            System.out.println("Error!");
        }
        return bigNumber;
    }
    /**
     * @param myPrime
     *            The latest prime to be found.
     * @param theBitSet
     *            The BitSet holding the prime flags
     * @param maxSize
     *            The largest index in the BitSet
     */
    static void sieveTheRest(int myPrime, BitSet theBitSet, int maxSize) {
        for (long k = myPrime * myPrime; k <= maxSize; k += 2 * myPrime) {
            theBitSet.clear((int) k);
        }
    }

}// End of Class eratosthenes5
\$\endgroup\$
4
\$\begingroup\$

You seem to have implemented it correctly from a complexity point of view, which is good.

I noticed a few things you could improve:

  • Why would a getTheMaxNumber method return a String? Why is the string called name?
  • You have a two page main() function, which then calls sieveTheRest. It would be nicer to just put all the sieving related code in one method.
  • You can also refactor your reporting code into a method of its own, this will make the main method more readable.
  • You don't win much performance by making 2 a special case. It just makes the code less readable.
  • You only find primes up to sqrt(name), why not all the way up to name?

Update:

Here is a very small implementation, which will set all primes in [0, maxNumber).

BitSet numbList = new BitSet(maxNumber);
numbList.set(2, maxNumber);
for (int i = 2; i < maxNumber; i++)
    if (numbList.get(i))
        for (int j = 2*i; j < maxNumber; j+=i)
            numbList.clear(j);

If you want the above to only run the outer loop up till sqrt(maxNumber), just change the first loop to for (int i = 2; i*i < maxNumber; i++). Just remember that any added complexity increases the chance of bugs.

\$\endgroup\$
  • \$\begingroup\$ I only went up to the sqrt(name) because when you reach that point all of the primes in the bitset have been found and there's no reason to go farther. You can then just use them or, in my case, report them. Making 2 a special case wasn't done for performance reasons, it was done simply because I didn't want to burden my sieve method with what I considered a special case which needed to be handled differently from all the other primes. \$\endgroup\$ – Mark Ross Jun 24 '14 at 14:14
  • \$\begingroup\$ Fair enough, but try to benchmark the code without it. The original 'Sieve of Eratosthenes' doesn't use this 'optimization', because the large numbers are passed so quickly, that their contribution to the running time should be insignificant. \$\endgroup\$ – Thomas Ahle Jun 24 '14 at 14:23
  • \$\begingroup\$ I tried benchmarking the code without the loop that marks all of the multiples of 2. It only ran about 5% slower, but I didn't like the way the code looked. In my view, the code is MORE readable this way. As far as what the 'original' Sieve of Eratosthenes uses, well, I wouldn't know, but I suspect that MOST of the optimizations I've added aren't in it. I still think I've stayed true to the intent of the algorithm. \$\endgroup\$ – Mark Ross Jun 25 '14 at 0:10
  • \$\begingroup\$ After working on this code for a while. I've found that it's far more 'fragile' than I would like. Indicates to me that there's something(s) I've overlooked. \$\endgroup\$ – Mark Ross Jun 25 '14 at 2:23
  • \$\begingroup\$ Ok, when I use my logic and try to let the sieve run up to 'name', it starts giving me incorrect results. It's like the index is 'wrapping' and clearing some previously marked primes. I guess I'll stay with my stopping point of sqrt(name) since that appears to give correct results up to the max integer I can give it. This is also about 40% faster than going all the way up to 'name'. \$\endgroup\$ – Mark Ross Jun 28 '14 at 5:27
1
\$\begingroup\$

I've been looking at your code and I find it very enlightening since I've never used BitSet.

I was wondering how the result could be saved in an external file for checking primality of numbers (up to ~800.000.000), which I guess would occupy around 100MB (around 100.000.000 bytes).

About the upper limit of the BitSet, I also think that it's the Java max integer size, since the constructor takes an integer. Maybe for larger sizes it could be implemented with an array of BitSet (first approach), even though the positions wouldn't be immediate then? Maybe I'll take a look at that after exams and let you know if I get to something solid.

\$\endgroup\$
  • \$\begingroup\$ Well, one possibility would be to just save the BitSet and read it in. It can currently identify around 105 million primes going up into the 2,000,000,000 neighborhood which would be enough for what you've stated. To verify a prime you can just check the BitSet location for that number. Unfortunately, how to save and restore the bitset is a little beyond me. You could use this code to regen it each time, I suppose, but would depend on your implementation. Good luck with it. \$\endgroup\$ – Mark Ross Jun 28 '14 at 21:58
  • \$\begingroup\$ Also, @Guimo, you CAN save substantial space in the BitSet by simply using it to represent the odd integers above 1. This can save a small amount of sieving time because you never have to sieve out the even numbers larger than 4. My final code runs in about 33 seconds, finding the primes up to 2,147,483,647. This is about 4 seconds faster than my version that represents all of the integers and has to filter the even numbers out. The big savings is that the new BitSet is about half the size (around 128 mb versus 256 mb). The numbers are messier, though, and harder to work with. \$\endgroup\$ – Mark Ross Jul 10 '14 at 22:44

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.