计算并打印第n个素数

Question

我正在尝试计算素数,我已经完成了.但我想计算并打印第n个素数(用户输入),在计算其余部分(它们不会被打印)时,只打印第n个素数.

这是我到目前为止所写的内容:

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\n");
        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("\n%d is prime", x);
            }
        }
    }
}

这是我编写的计算从1到n的素数的程序.但是,我希望它只打印第n个素数,

我想到的是在每次找到素数时都会对它进行某种计算和计算,当计数== n然后它打印出那个数字,但是我无法弄清楚如何降落它.

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 school¹, 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 - ?(n²*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 ...

等一下!我们有2 <-> n/2和3 <-> n/3.n的除数成对出现.

如果我们考虑对(d, n/d)相应的除数n,要么d = n/d,即d = ?n,或其中之一,比方说d,比其他较小.但是然后d*d < d*(n/d) = n和d < ?n.每对相应的除数n包含(至少)一个不超过的除数?n.

如果 n 是复合的,则其最小的非平凡除数不超过 ?n.

因此,我们可以减少循环限制?n,并降低算法的运行时复杂性.它现在应该是？(n ^1.5*？(log n)),但从经验上来看似乎更好一点 - 但是,没有足够的数据从实证结果中得出可靠的结论.

它在大约16秒内找到了百万分之一的素数,在不到9分钟的时间内找到了第一百万分之一,并且在大约四个半小时内找到了百万分之一.这仍然很慢,但与十年左右相比,它需要天真的试验师.

由于有素数的正方形和两个接近素数的乘积,如323 = 17*19,我们无法减少下面的试验分割循环的限制?n.因此,在试用分区的同时,我们必须寻找其他方法来改进算法.

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;
}

这给我们带来了另一个加速因子(接近)1.5,因此我们需要大约一个半小时才能达到数亿分之一.

如果我们继续这条路线,下一步就是消除5的倍数.互数为2,3和5的数字是表格的数字

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) hold? Unfortunately, there are composite numbers - Carmichael numbers - such that the congruence holds for every a coprime to n. That means that to identify a Carmichael number as composite with the Fermat test, we have to pick a base that is a multiple of one of n's prime divisors - there may not be many such multiples.

But we can strengthen the Fermat test so that composites are more reliably detected. If p is an odd prime, write p-1 = 2*m. Then, if 0 < a < p,

a^(p-1) - 1 = (a^m + 1) * (a^m - 1)

and p divides exactly one of the two factors (the two factors differ by 2, so their greatest common divisor is either 1 or 2). If m is even, we can split a^m - 1 in the same way. Continuing, if p-1 = 2^s * k with k odd, write

a^(p-1) - 1 = (a^(2^(s-1)*k) + 1) * (a^(2^(s-2)*k) + 1) * ... * (a^k + 1) * (a^k - 1)

then p divides exactly one of the factors. This gives rise to the strong Fermat test,

Let n > 2 be an odd number. Write n-1 = 2^s * k with k odd. Given any a with 1 < a < n-1, if

1. a^k ? 1 (mod n) or
2. a^((2^j)*k) ? -1 (mod n) for any j with 0 <= j < s

then n is a strong (Fermat) probable prime for base a. A composite strong base a (Fermat) probable prime is called a strong (Fermat) pseudoprime for the base a. Strong Fermat pseudoprimes are even rarer than ordinary Fermat pseudoprimes, below 1000000, there are 78498 primes, 245 base-2 Fermat pseudoprimes and only 46 base-2 strong Fermat pseudoprimes. More importantly, for any odd composite n, there are at most (n-9)/4 bases 1 < a < n-1 for which n is a strong Fermat pseudoprime.

So if n is an odd composite, the probability that n passes k strong Fermat tests with randomly chosen bases between 1 and n-1 (exclusive bounds) is less than 1/4^k.

A strong Fermat test takes O(log n) steps, each step involves one or two multiplications of numbers with O(log n) bits, so the complexity is O((log n)^3) with naive multiplication [for huge n, more sophisticated multiplication algorithms can be worthwhile].

The Miller-Rabin test is the k-fold strong Fermat test with randomly chosen bases. It is a probabilistic test, but for small enough bounds, short combinations of bases are known which give a deterministic result.

Strong Fermat tests are part of the deterministic APRCL test.

It is advisable to precede such tests with trial division by the first few small primes, since divisions are comparatively cheap and that weeds out most composites.

For the problem of finding the n^th prime, in the range where testing all numbers for primality is feasible, there are known combinations of bases that make the multiple strong Fermat test correct, so that would give a faster - O(n*(log n)⁴) - algorithm.

For n < 2^32, the bases 2, 7, and 61 are sufficient to verify primality. Using that, the hundred-millionth prime is found in about six minutes.

Eliminating composites by prime divisors, the Sieve of Eratosthenes

Instead of investigating the numbers in sequence and checking whether each is prime from scratch, one can also consider the whole set of relevant numbers as one piece and eliminate the multiples of a given prime in one go. This is known as the Sieve of Eratosthenes:

To find the prime numbers not exceeding N

1. make a list of all numbers from 2 to N
2. for each k from 2 to N: if k is not yet crossed off, it is prime; cross off all multiples of k as composites

The primes are the numbers in the list which aren't crossed off.

This algorithm is fundamentally different from trial division, although both directly use the divisibility characterisation of primes, in contrast to the Fermat test and similar tests which use other properties of primes.

In trial division, each number n is paired with all primes not exceeding the smaller of ?n and the smallest prime divisor of n. Since most composites have a very small prime divisor, detecting composites is cheap here on average. But testing primes is expensive, since there are relatively many primes below ?n. Although there are many more composites than primes, the cost of testing primes is so high that it completely dominates the overall running time and renders trial division a relatively slow algorithm. Trial division for all numbers less than N takes O(N^1.5/(log N)²) steps.

In the sieve, each composite n is paired with all of its prime divisors, but only with those. Thus there the primes are the cheap numbers, they are only ever looked at once, while the composites are more expensive, they are crossed off multiple times. One might believe that since a sieve contains many more 'expensive' numbers than 'cheap' ones, it would overall be a bad algorithm. However, a composite number does not have many distinct prime divisors - the number of distinct prime divisors of n is bounded by log n, but usually it is much smaller, the average of the number of distinct prime divisors of the numbers <= n is log log n - so even the 'expensive' numbers in the sieve are on average no more (or hardly more) expensive than the 'cheap' numbers for trial division.

Sieving up to N, for each prime p, there are ?(N/p) multiples to cross off, so the total number of crossings-off is ?(? (N/p)) = ?(N * log (log N)). This yields much faster algorithms for finding the primes up to N than trial division or sequential testing with the faster primality tests.

There is, however, a disadvantage to the sieve, it uses O(N) memory. (But with a segmented sieve, that can be reduced to O(?N) without increasing the time complexity.)

For finding the n^th prime, instead of the primes up to N, there is also the problem that it is not known beforehand how far the sieve should reach.

The latter can be solved using the prime number theorem. The PNT says

?(x) ~ x/log x (equivalently: lim ?(x)*log x/x = 1),

where ?(x) is the number of primes not exceeding x (here and below, log must be the natural logarithm, for the algorithmic complexities it is not important which base is chosen for the logarithms). From that, it follows that p(n) ~ n*log n, where p(n) is the n^th prime, and there are good upper bounds for p(n) known from deeper analysis, in particular

n*(log n + log (log n) - 1) < p(n) < n*(log n + log (log n)), for n >= 6.

So one can use that as the sieving limit, it doesn't exceed the target far.

The O(N) space requirement can be overcome by using a segmented sieve. One can then record the primes below ?N for O(?N / log N) memory consumption and use segments of increasing length (O(?N) when the sieve is near N).

There are some easy improvements on the algorithm as stated above:

1. start crossing off multiples of p only at p², not at 2*p
2. eliminate the even numbers from the sieve
3. eliminate the multiples of further small primes from the sieve

None of these reduce the algorithmic complexity, but they all reduce the constant factors by a significant amount (as with trial division, the elimination of multiples of p yields lesser speedup for larger p while increasing the code complexity more than for smaller p).

Using the first two improvements yields

// Entry k in the array represents the number 2*k+3, so we have to do
// a bit of arithmetic to get the indices right.
public static int nthPrime(int n) {
    if (n < 2) return 2;
    if (n == 2) return 3;
    int limit, root, count = 1;
    limit = (int)(n*(Math.log(n) + Math.log(Math.log(n)))) + 3;
    root = (int)Math.sqrt(limit) + 1;
    limit = (limit-1)/2;
    root = root/2 - 1;
    boolean[] sieve = new boolean[limit];
    for(int i = 0; i < root; ++i) {
        if (!sieve[i]) {
            ++count;
            for(int j = 2*i*(i+3)+3, p = 2*i+3; j < limit; j += p) {
                sieve[j] = true;
            }
        }
    }
    int p;
    for(p = root; count < n; ++p) {
        if (!sieve[p]) {
            ++count;
        }
    }
    return 2*p+1;
}

which finds the hundred-millionth prime, 2038074743, in about 18 seconds. This time can be reduced to about 15 seconds (here, YMMV) by storing the flags packed, one bit per flag, instead of as booleans, since the reduced memory usage gives better cache locality.

Packing the flags, eliminating also multiples of 3 and using bit-twiddling for faster faster counting,

// Count number of set bits in an int
public static int popCount(int n) {
    n -= (n >>> 1) & 0x55555555;
    n = ((n >>> 2) & 0x33333333) + (n & 0x33333333);
    n = ((n >> 4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F);
    return (n * 0x01010101) >> 24;
}

// Speed up counting by counting the primes per
// array slot and not individually. This yields
// another factor of about 1.24 or so.
public static int nthPrime(int n) {
    if (n < 2) return 2;
    if (n == 2) return 3;
    if (n == 3) return 5;
    int limit, root, count = 2;
    limit = (int)(n*(Math.log(n) + Math.log(Math.log(n)))) + 3;
    root = (int)Math.sqrt(limit);
    switch(limit%6) {
        case 0:
            limit = 2*(limit/6) - 1;
            break;
        case 5:
            limit = 2*(limit/6) + 1;
            break;
        default:
            limit = 2*(limit/6);
    }
    switch(root%6) {
        case 0:
            root = 2*(root/6) - 1;
            break;
        case 5:
            root = 2*(root/6) + 1;
            break;
        default:
            root = 2*(root/6);
    }
    int dim = (limit+31) >> 5;
    int[] sieve = new int[dim];
    for(int i = 0; i < root; ++i) {
        if ((sieve[i >> 5] & (1 << (i&31))) == 0) {
            int start, s1, s2;
            if ((i & 1) == 1) {
                start = i*(3*i+8)+4;
                s1 = 4*i+5;
                s2 = 2*i+3;
            } else {
                start = i*(3*i+10)+7;
                s1 = 2*i+3;
                s2 = 4*i+7;
            }
            for(int j = start; j < limit; j += s2) {
                sieve[j >> 5] |= 1 << (j&31);
                j += s1;
                if (j >= limit) break;
                sieve[j >> 5] |= 1 << (j&31);
            }
        }
    }
    int i;
    for(i = 0; count < n; ++i) {
        count += popCount(~sieve[i]);
    }
    --i;
    int mask = ~sieve[i];
    int p;
    for(p = 31; count >= n; --p) {
        count -= (mask >> p) & 1;
    }
    return 3*(p+(i<<5))+7+(p&1);
}

finds the hundred-millionth prime in about 9 seconds, which is not unbearably long.

There are other types of prime sieves, of particular interest is the Sieve of Atkin, which exploits the fact that certain congruence classes of (rational) primes are composites in the ring of algebraic integers of some quadratic extensions of ?. Here is not the place to expand on the mathematical theory, suffice it to say that the Sieve of Atkin has lower algorithmic complexity than the Sieve of Eratosthenes and hence is preferable for large limits (for small limits, a not overly optimised Atkin sieve has higher overhead and thus can be slower than a comparably optimised Eratosthenes sieve). D. J. Bernstein's primegen library (written in C) is well optimised for

Answer 2

int counter = 0;

for(int i = 1; ; i++) {
    if(isPrime(i)
        counter++;

    if(counter == userInput) {
        print(i);
        break;
    }
}

编辑:你的主要功能可以使用一些工作.这是我写的一篇:

private static boolean isPrime(long n) {
    if(n < 2)
        return false;

    for (long i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

注意 - 在查看因子时,您只需要达到sqrt(n),因此 i * i <= n

Answer 3

你试图在main方法中做太多.您需要将其分解为更易于管理的部分.编写一个方法boolean isPrime(int n),如果数字是素数则返回true,否则返回false.然后修改main方法以使用isPrime.