java - Calculating and printing the nth prime number

Question

I am trying to calculate prime numbers, which I've already done. But I want to calculate and print ONLY the nth prime number (User input), while calculating the rest (They won't be printed) only the nth prime number will be printed.

Here's what I've written so far:

import java.util.Scanner;
/**
 * Calculates the nth prime number
 * @author {Zyst}
 */
public class Prime {
    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        int n, 
            i = 2, 
            x = 2;

        System.out.printf("This program calculates the nth Prime number
");
        System.out.printf("Please enter the nth prime number you want to find: ");
        n = input.nextInt();

        for(i = 2, x = 2; i <= n; i++) {
            for(x = 2; x < i; x++) {
                if(i % x == 0) {
                    break;
                }
            }
            if(x == i) {
                System.out.printf("
%d is prime", x);
            }
        }
    }
}

This is the program I wrote to calculate the prime numbers from 1 to n. However, I want it to only print the nth prime number,

What I've thought of doing is making some sort of count int and ++ing it every time it finds a prime, and when the count == n then it prints out that number, but I can't quite figure out how to land it.

Answer 1

To calculate the n-th prime, I know two main variants.

The straightforward way

That is to count all the primes starting from 2 as you find them until you have reached the desired n^th.

This can be done with different levels of sophistication and efficiency, and there are two conceptually different ways to do it. The first is

Testing the primality of all numbers in sequence

This would be accomplished by a driver function like

public static int nthPrime(int n) {
    int candidate, count;
    for(candidate = 2, count = 0; count < n; ++candidate) {
        if (isPrime(candidate)) {
            ++count;
        }
    }
    // The candidate has been incremented once after the count reached n
    return candidate-1;
}

and the interesting part that determines the efficiency is the isPrime function.

The obvious way for a primality check, given the definition of a prime as a number greater than 1 that is divisible only by 1 and by itself that we learned in school1, is

Trial division

The direct translation of the definition into code is

private static boolean isPrime(int n) {
    for(int i = 2; i < n; ++i) {
        if (n % i == 0) {
            // We are naive, but not stupid, if
            // the number has a divisor other
            // than 1 or itself, we return immediately.
            return false;
        }
    }
    return true;
}

but, as you will soon discover if you try it, its simplicity is accompanied by slowness. With that primality test, you can find the 1000^th prime, 7919, in a few milliseconds (about 20 on my computer), but finding the 10000^th prime, 104729, takes seconds (~2.4s), the 100000^th prime,1299709, several minutes (about 5), the millionth prime, 15485863, would take about eight and a half hours, the ten-millionth prime, 179424673, weeks, and so on. The runtime complexity is worse than quadratic - Θ(n2 * log n).

So we'd like to speed the primality test up somewhat. A step that many people take is the realisation that a divisor of n (other than n itself) can be at most n/2. If we use that fact and let the trial division loop only run to n/2 instead of n-1, how does the running time of the algorithm change? For composite numbers, the lower loop limit doesn't change anything. For primes, the number of trial divisions is halved, so overall, the running time should be reduced by a factor somewhat smaller than 2. If you try it out, you will find that the running time is almost exactly halved, so almost all the time is spent verifying the primality of primes despite there being many more composites than primes.

Now, that didn't help much if we want to find the one-hundred-millionth prime, so we have to do better. Trying to reduce the loop limit further, let us see for what numbers the upper bound of n/2 is actually needed. If n/2 is a divisor of n, then n/2 is an integer, in other words, n is divisible by 2. But then the loop doesn't go past 2, so it never (except for n = 4) reaches n/2. Jolly good, so what's the next largest possible divisor of n? Why, n/3 of course. But n/3 can only be a divisor of n if it is an integer, in other words, if n is divisible by 3. Then the loop will exit at 3 (or before, at 2) and never reach n/3 (except for n = 9). The next largest possible divisor ...

Hang on a minute! We have 2 <-> n/2 and 3 <-> n/3. The divisors of n come in pairs.

If we consider the pair (d, n/d) of corresponding divisors of n, either d = n/d, i.e. d = √n, or one of them, say d, is smaller than the other. But then d*d < d*(n/d) = n and d < √n. Each pair of corresponding divisors of n contains (at least) one which does not exceed √n.

If n is composite, its smallest nontrivial divisor does not exceed √n.

So we can reduce the loop limit to √n, and that reduces the runtime complexity of the algorithm. It should now be Θ(n^1.5 * √(log n)), but empirically it seems to scale a little bit better - however, there's not enough data to draw reliable conclusions from empirical results.

That finds the millionth prime in about 16 seconds, the ten-millionth in just under nine minutes, and it would find the one-hundred-millionth in about four and a half hours. That's still slow, but a far cry from the ten years or so it would take the naive trial division.

Since there are squares of primes and products of two close primes, like 323 = 17*19, we cannot reduce the limit for the trial division loop below √n. Therefore, while staying with trial division, we must look for other ways to improve the algorithm now.

One easily seen thing is that no prime other than 2 is even, so we need only check odd numbers after we have taken care of 2. That doesn't make much of a difference, though, since the even numbers are the cheapest to find composite - and the bulk of time is still spent verifying the primality of primes. However, if we look at the even numbers as candidate divisors, we see that if n is divisible by an even number, n itself must be even, so (excepting 2) it will have been recognised as composite before division by any even number greater than 2 is attempted. So all divisions by even numbers greater than 2 that occur in the algorithm must necessarily leave a nonzero remainder. We can thus omit these divisions and check for divisibility only by 2 and the odd numbers from 3 to √n. This halves (not quite exactly) the number of divisions required to determine a number as prime or composite and therefore the running time. That's a good start, but can we do better?

Another large family of numbers is the multiples of 3. Every third division we perform is by a multiple of 3, but if n is divisible by one of them, it is also divisible by 3, and hence no division by 9, 15, 21, ... that we perform in our algorithm will ever leave a remainder of 0. So, how can we skip these divisions? Well, the numbers divisible by neither 2 nor 3 are precisely the numbers of the form 6*k ± 1. Starting from 5 (since we're only interested in numbers greater than 1), they are 5, 7, 11, 13, 17, 19, ..., the step from one to the next alternates between 2 and 4, which is easy enough, so we can use

private static boolean isPrime(int n) {
    if (n % 2 == 0) return n == 2;
    if (n % 3 == 0) return n == 3;
    int step = 4, m = (int)Math.sqrt(n) + 1;
    for(int i = 5; i < m; step = 6-step, i += step) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

This gives us another speedup by a factor of (nearly) 1.5, so we'd need about one and a half hours to the hundred-millionth prime.

If we continue this route, the next step is the elimination of multiples of 5. The numbers coprime to 2, 3 and 5 are the numbers of the form

30*k + 1, 30*k + 7, 30*k + 11, 30*k + 13, 30*k + 17, 30*k + 19, 30*k + 23, 30*k + 29

so we'd need only divide by eight out of every thirty numbers (plus the three smallest primes). The steps from one to the next, starting from 7, cycle through 4, 2, 4, 2, 4, 6, 2, 6. That's still easy enough to implement and yields another speedup by a factor of 1.25 (minus a bit for more complicated code). Going further, the multiples of 7 would be eliminated, leaving 48 out of every 210 numbers to divide by, then 11 (480/2310), 13 (5760/30030) and so on. Each prime p whose multiples are eliminated yields a speedup of (almost) p/(p-1), so the return decreases while the cost (code complexity, space for the lookup table for the steps) increases with each prime.

In general, one would stop soonish, after eliminating the multiples of maybe six or seven primes (or even fewer). Here, however, we can follow through to the very end, when the multiples of all primes have been eliminated and only the primes are left as candidate divisors. Since we are finding all primes in order, each prime is found before it is needed as a candidate divisor and can then be stored for future use. This reduces the algorithmic complexity to - if I haven't miscalculated - O(n^1.5 / √(log n)). At the cost of space usage for storing the primes.

With trial division, that is as good as it gets, you have to try and divide by all primes to √n or the first dividing n to determine the primality of n. That finds the hundred-millionth prime in about half an hour here.

So how about

Fast primality tests

Primes have other number-theoretic properties than the absence of nontrivial divisors which composite numbers usually don't have. Such properties, if they are fast to check, can form the basis of probabilistic or deterministic primality tests. The archetypical such property is associated with the name of Pierre de Fermat, who, in the early 17^th century, found that

If p is a prime, then p is a divisor of (a^p-a) for all a.

This - Fermat's so-called 'little theorem' - is, in the equivalent formulation

Let p be a prime and a not divisible by p. Then p divides a^p-1 - 1.

the basis of most of the widespread fast primality tests (for example Miller-Rabin) and variants or analogues of that appear in even more (e.g. Lucas-Selfridge).

So if we want to know if a not too small odd number n is a prime (even and small numbers are efficiently treated by trial division), we can choose any number a (> 1) which is not a multiple of n, for example 2, and check whether n divides a^n-1 - 1. Since a^n-1 becomes huge, that is most efficiently done by checking whether a^(n-1) ≡ 1 (mod n), i.e. by modular exponentiation. If that congruence doesn't hold, we know that n is composite. If it holds, however, we cannot conclude that n is prime, for example 2^340 ≡ 1 (mod 341), but 341 = 11 * 31 is composite. Composite numbers n such that a^(n-1) ≡ 1 (mod n) are called Fermat pseudoprimes for the base a.

But such occurrences are rare. Given any base a > 1, although there are an infinite number of Fermat pseudoprimes to base a, they are much rarer than actual primes. For example, there are only 78 base-2 Fermat pseudoprimes and 76 base-3 Fermat pseudoprimes below 100000, but 9592 primes. So if one chooses an arbitrary odd n > 1 and an arbitrary base a > 1 and finds a^(n-1) ≡ 1 (mod n), there's a good chance that n is actually prime.

However, we are in a slightly different situation, we are given n and can only choose a. So, for an odd composite n, for how many a, 1 < a < n-1 can a^(n-1) ≡ 1 (mod n)</cod