Submitting a Java program which implements the Sieve of Eratosthenes

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

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.

StackExchange Code Review Q#55086, answer score: 4