Finding the list of prime numbers in shortest time

Question

I read lot many algorithms to find prime numbers and the conclusion is that a number is a prime number if it is not divisible by any of its preceding prime numbers.

I am not able to find a more precise definition. Based on this I have written a code and it performs satisfactory till the max number I pass is 1000000. But I believe there are much faster algorithms to find all primes lesser than a given number.

Following is my code, can I have a better version of the same?

 public static void main(String[] args) {
    for (int i = 2; i < 100000; i++) {
        if (checkMod(i)) {
            primes.add(i);
        }
    }
}

private static boolean checkMod( int num) {
    for (int i : primes){
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

Answer 1

The good thing in your primality test is that you only divide by primes.

private static boolean checkMod( int num) {
    for (int i : primes){
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

The bad thing is that you divide by all primes found so far, that is, all primes smaller than the candidate. That means that for the largest prime below one million, 999983, you divide by 78497 primes to find out that this number is a prime. That's a lot of work. So much, in fact, that the work spent on primes in this algorithm accounts for about 99.9% of all work when going to one million, a larger part for higher limits. And that algorithm is nearly quadratic, to find the primes to n in this way, you need to perform about

n² / (2*(log n)²)

divisions.

A simple improvement is to stop the division earlier. Let n be a composite number (i.e. a number greter than 1 that has divisors other than 1 and n), and let d be a divisor of n.

Now, d being a divisor of n means that n/d is an integer, and also a divisor of n: n/(n/d) = d. So we can naturally group the divisors of n into pairs, each divisor d gives rise to the pair (d, n/d).

For such a pair, there are two possibilities:

1. d = n/d, which means n = d², or d = √n.
2. The two are different, then one of them is smaller than the other, say d < n/d. But that immediately translates to d² < n or d < √n.

So, either way, each pair of divisors contains (at least) one not exceeding √n, hence, if n is a composite number, its smallest divisor (other than 1) does not exceed √n.

So we can stop the trial division when we've reached √n:

private static boolean checkMod( int num) {
    for (int i : primes){
        if (i*i > n){
            // We have not found a divisor less than √n, so it's a prime
            return true;
        }
        if( num % i == 0){
            return false;
        }
    }
    return true;
}

Note: That depends on the list of primes being iterated in ascending order. If that is not guaranteed by the language, you have to use a different method, iterate by index through an ArrayList or something like that.

Stopping the trial division at the square root of the candidate, for the largest prime below one million, 999983, we now only need to divide it by the 168 primes below 1000. That's a lot less work than previously. Stopping the trial division at the square root, and dividing only by primes, is as good as trial division can possibly get and requires about

2*n^1.5 / (3*(log n)²)

divisions, for n = 1000000, that's a factor of about 750, not bad, is it?

But that's still not very efficient, the most efficient methods to find all primes below n are sieves. Simple to implement is the classical Sieve of Eratosthenes. That finds the primes below n in O(n*log log n) operations, with some enhancements (eliminating multiples of several small primes from consideration in advance), its complexity can be reduced to O(n) operations. A relatively new sieve with better asymptotic behaviour is the Sieve of Atkin, which finds the primes to n in O(n) operations, or with the enhancement of eliminating the multiples of some small primes, in O(n/log log n) operations. The Sieve of Atkin is more complicated to implement, so it's likely that a good implementation of a Sieve of Eratosthenes performs better than a naive implementation of a Sieve of Atkin. For implementations of like optimisation levels, the performance difference is small unless the limit becomes large (larger than 10¹⁰; and it's not uncommon that in practice, a Sieve of Eratosthenes scales better than a Sieve of Atkin beyond that, due to better memory access patterns). So I would recommend beginning with a Sieve of Eratosthenes, and only when its performance isn't satisfactory despite honest efforts at optimisation, delve into the Sieve of Atkin. Or, if you don't want to implement it yourself, find a good implementation somebody else has already seriously tuned.

I have gone into a bit more detail in an answer with a slightly different setting, where the problem was finding the n-th prime. Some implementations of more-or-less efficient methods are linked from that answer, in particular one or two usable (though not much optimised) implementations of a Sieve of Eratosthenes.