Sieve of Eratosthenes and twin prime finder

Question

I made this program to find primes and twin pairs. I'd like feedback on anything from formatting to content to technique. In short: how would this be different if it was written by an experienced professional?

The program runs five methods:

• getMax asks for an integer input which is the maximum number below which to find primes and twin prime pairs. It also has an error message to catch unacceptable input and ask again.
• sieve checks every number between 0 and max and returns a boolean array which says whether each index is prime or not.
• primesCount counts many primes there are, and prints it.
• primesList creates an integer array of all primes, and prints it.
• pairsCount counts how many twin prime pairs there are, and prints it.
• pairsList creates a string array of all twin prime pairs, and prints it.

Code:

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    int max = getMax(in);

    boolean[] primesSieve = sieve(max);        
    int primesCount = primesCount(primesSieve);
    int[] primesList = primesList(primesSieve, primesCount);
    int pairsCount = pairsCount(primesList);
    pairsList(primesList, pairsCount);

}   

// User input for maximum number to sieve
public static int getMax(Scanner in) {      
    System.out.print("Maximum number to sieve: ");
    while (!in.hasNextInt()) {
        String input = in.next();
        System.out.println("Error: \"" + input + "\" is not a number. Try again.");
        System.out.print("Maximum number to sieve: ");
    }
    int max = in.nextInt();
    return max;
}

// Create boolean array of prime status of integers less than max
public static boolean[] sieve(int max) {

    // Create initial array and assume all are primes
    boolean[] arePrimes = new boolean[max];
    for (int i = 0; i<max; i++) {
        arePrimes[i] = true;
    }

    // Mark multiples of each prime as non-prime
    for (int i = 2; i<max; i++) {
        if (arePrimes[i]) {
            for (int m = 2; i * m < max; m++) {
                arePrimes[i*m] = false;
            }
        }
    }
    return arePrimes;
}

// Count and print how many primes are less than max    
public static int primesCount(boolean[] primes) {
    int count = 0;
    for (boolean prime : primes) {
        if (prime) {
            count++;
        }
    }
    System.out.println("Number of primes: " + count);
    return count;
}

// Create and print array listing all primes less than max
public static int[] primesList(boolean[] sievedPrimes, int numberOfPrimes) {
    int[] listPrimes = new int[numberOfPrimes-2];
    int n = 0;

    for (int i=2; i<sievedPrimes.length; i++) {
        if (sievedPrimes[i]) {
            listPrimes[n] = i;
            n++;
        }   
    }
    System.out.println("List of primes: " + Arrays.toString(listPrimes));
    return listPrimes;
}

// Count and print the number of twin prime pairs
public static int pairsCount(int[] listOfPrimes) {
    int pairsCount = 0;
    for (int i=0; i<listOfPrimes.length-1; i++) {
        if (listOfPrimes[i+1] - listOfPrimes[i] == 2) {
            pairsCount++;
        }
    }
    System.out.println("Number of twin prime pairs: " + pairsCount);
    return pairsCount;
}

// Create and print array listing all pairs of twin primes less than max
public static String[] pairsList(int[] listOfPrimes, int pairsCount) {
    String[] twinPrimes = new String[pairsCount];
    int n = 0;
    for (int i=0; i<listOfPrimes.length-1; i++) {
        if (listOfPrimes[i+1] - listOfPrimes[i] == 2) {
            twinPrimes[n] = listOfPrimes[i] + " and " + listOfPrimes[i+1];
            n++;
        }
    }
    System.out.println("List of twin prime pairs: " + Arrays.toString(twinPrimes));
    return twinPrimes;
}

Answer 1

Implementation

// Mark multiples of each prime as non-prime
for (int i = 2; i<max; i++) {
    if (arePrimes[i]) {
        for (int m = 2; i * m < max; m++) {
            arePrimes[i*m] = false;
        }
    }
}

Pretty close to the perfect implementation.

However...

Consider the Transitive relation of the multiplication operation: 5 times 2 is 10. 2 times 5 is 10. It doesn't matter in which order you multiply things.

So when you multiply, say, 3 by 2, you're just multiplying 2 by 3 again. And the same goes for 5 by 2, 7 by 2, 11 by 2... but also 5 by 3, 7 by 3, 7 by 5, etc.

What you'd do in this case is start m off at the value of i. This solves the issue where you're multiplying 2 with 3 and 3 with 2, thus checking the same thing twice.

There's another issue: Now that we're effectively checking (i * i) < max in the inner loop on the first iteration, it doesn't make sense for the outer loop to check for on i < max. Instead, you'd want to check for (i * i) < max there as well.

// Mark multiples of each prime as non-prime
for (int i = 2; i * i < max; i++) {
    if (arePrimes[i]) {
        for (int m = i; i * m < max; m++) {
            arePrimes[i*m] = false;
        }
    }
}

---

I was also a bit worried about getMax willing to accept negative numbers, but Java will throw a java.lang.NegativeArraySizeException, and as such, the error should be pretty clear. For use in a larger application, you might want to handle the exception, rather than the program forcibly exiting.

Documentation

You should use Javadoc style comments. Simple //comments before each function generally don't get picked up by IDE's. By making use of Javadoc, you can provide descriptions of what a method does and what the meaning of each parameter is. Like that, not only will other programmers easily be able to search for information in a method's documentation, it can also be automated - like an IDE showing a tooltip for each method parameter as you type them.

Answer 2

Efficient loops

This is more of an addendum to @Pimgd's answer. He suggested this:

// Mark multiples of each prime as non-prime
for (int i = 2; i * i < max; i++) {
    if (arePrimes[i]) {
        for (int m = i; i * m < max; m++) {
            arePrimes[i*m] = false;
        }
    }
}

If you look at the inner loop, it does two multiplies and one add per iteration. You could do remove the multiplications like this:

// Mark multiples of each prime as non-prime
for (int i = 2; i * i < max; i++) {
    if (arePrimes[i]) {
        for (int m = i*i; m < max; m += i) {
            arePrimes[m] = false;
        }
    }
}

This leaves just one addition per loop iteration. Furthermore, if you first mark all the even numbers as nonprimes, you could make both the inner and outer loops 2x faster by skipping even numbers (in each loop):

// Mark multiples of each prime as non-prime
for (int i = 3; i * i < max; i += 2) {
    if (arePrimes[i]) {
        int increment = i + i;
        for (int m = i*i; m < max; m += increment) {
            arePrimes[m] = false;
        }
    }
}

Further optimizations

Other optimizations you could make would be:

1. Using one bit per prime instead of one boolean to save space and improve caching.
2. Using wheel factorization in conjunction with the sieve.