Finding the first 10 million primes

Question

I'm trying to find the first 100 million primes and am trying to find the most efficient way to do it. Can I get some advice on how I could improve this?

public class Main {

    public static void main(String[] args) {

        int counter = 0;
        int num = 3;
        int index = 1;
        int[] primes = new int[100000000];
        primes[0] = 2;

        while(counter < 99999999){
            if(isPrime(num)) {
                primes[index] = num;
                index++;
                counter++;
            }
            num+=2;
        }
        index = 1;
        for (int i : primes) {
            System.out.println(String.format("%d: %d", index, i));
            index++;
        }
    }

    private static boolean isPrime(int num){
        if (num < 2) return false;
        else if (num == 2) return true;
        for (int i = 2; i < num; i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}

Answer 1

Readability

        int counter = 0;
        int num = 3;
        int index = 1;
        int[] primes = new int[100000000];
        primes[0] = 2;

I find this order confusing. Consider

        // 2 is the first prime and the only one that is even, so process it separately
        int[] primes = new int[100000000];
        primes[0] = 2;
        int index = 1;

        // 3 is the next prime after 2; i.e. the first odd prime
        int candidate = 3;

Oops, did I forget something? What happened to counter? I took it out entirely as unnecessary. As it was only used in the loop, if I had included it, it would have looked like

        for (int counter = 1; counter < primes.length; ) {

And I would have replaced the while loop as well. But I actually think that it's easier to just remove counter and use index instead. More on that later.

By breaking the code up into clumps and adding comments, it is easier to see how the lines of code relate to each other. It was not obvious to me on first read that index indexed primes. Now that is much clearer. And it is clearer why it starts at 1 rather than 0.

I prefer the name candidate to num. It is clearer about what is being tracked there.

Robustness

        while(counter < 99999999){

Why 99999999? After staring at it for a bit, I realized that this is because counter is only counting the numbers after 2. Why? I would find it easier to say and understand

    while (index < primes.length) {

First I tried it with counter set to 1 initially. But then I realized that that made counter an exact duplicate of index. So we can ditch counter entirely.

For either, it is more robust to limit by primes.length. In the original code, if you changed the length of primes, you had to manually change the loop definition to match. This way, it will match automatically.

I also find it clearer to limit based on index, as that is what is actually problematic.

Delegate

Consider replacing the entire body of the main method with two method calls.

        int[] primes = findPrimes(100000000);
        displayPrimes(primes);

Now the main method itself does just one thing, call two methods. Each method can do just one thing:

1. Set the primes array.
2. Display the primes.

Even better might be to add a Primes class.

        Primes primes = new Primes(100000000);
        primes.initialize();
        primes.display();

This also offers some efficiency optimizations that static methods don't. More on that later.

Optimization

But your real question was optimization, so let's think about that.

All your candidates are going to be odd numbers. You already took advantage of the fact that 2 is the only even prime. You can take advantage of that again by rewriting isPrime to

    public static boolean isPrime(int candidate) {
        // 2 is the only even prime
        if (candidate % 2 == 0) {
            return candidate == 2;
        }

        if (candidate < 2) {
            return false;
        }

        return isOddPrime(candidate);
    }

And then

    // only returns useful results for odd numbers equal to 3 or more.
    private static boolean isOddPrime(int candidate) {
        for (int factor = 3; factor <= candidate / factor; factor += 2) {
            if (candidate % factor == 0) {
                return false;
            }
        }

        return true;
    }

How does this help? Notice that the situations checked in isPrime will never return true for your candidates. The smallest one is 3, so never less than or equal to 2. You increment by 2, so never even. So it will always drop through to the isOddPrime check. Therefore, we can replace the isPrime call with an isOddPrime with no change in results.

And isOddPrime is more efficient.

1. It saves a modulus operation and two comparisons.

   This should be obvious. Those are in isPrime prior to the call to isOddPrime. There's a third comparison that never runs on these candidates anyway, so we won't count that.

2. It only checks every other number, as it can skip all the even factors.

   It uses the same start at 3 and increment by 2 logic as the main method.

3. It only checks factors up to the square root of the candidate.

   This is probably the least obvious. But factor <= candidate / factor is the equivalent of factor * factor <= candidate or factor <= sqrt(candidate) for all positive values of factor.

   We can do this safely because at least one of any pair of factors must be less than or equal to the square root. Otherwise their product will be greater than the number.

   This won't matter much at the beginning, but there is a big difference between checking every number up to a thousand and every number up to a million.

Alternative

Instead of creating a new candidate factors list each time, use your primes instead. This works best if you have a separate primes' class with something like

    int[] primes;

    public PrimesList(int size) {
        primes = new int[size];
    }

Now primes is available to every non-static method in the class. So your isOddPrime could become

    private boolean isOddPrime(int candidate) {
        for (int prime : primes) {
            if (prime > candidate / prime) {
                return true;
            }

            if (candidate % prime == 0) {
                return false;
            }
        }

        return true;
    }

This saves checking non-prime odd numbers like 9, 15, 21, etc. Those will never work because you already checked their factors. E.g. for 35, you already checked that it's not divisible by 5 and 7, so you already know that 35 won't work.

Further

You optimized out even numbers. It's also possible to optimize out candidates divisible by three. Instead of incrementing by 2 every time, you can increment by 2 and then 4 and repeat that cycle. So you'd check 5, 7, skip 9, 11, 13, skip 15, etc. I won't go into this here, as it probably doesn't add much performance. But here is an example that uses this optimization.

Sieve

The Sieve of Eratosthenes is another possibility, but sieves don't do so well with limits on the number of primes. They are designed to be limited by the candidate pool. So you might find yourself needing to implement a sieve with a rolling segment. That's extra work, so you might prefer to avoid it.

An example of a windowed sieve that you could modify to work by segments.