Generating prime numbers in poly-time

Question

I am struggling to see how we can generate a list of J smallest primes in poly-time J, based on the fact that p'j is less than or equal to 2j * ln(j) for j > 2, where j indicates the j-th consecutive prime number. For instance, p1 = 2 for j=1, p2 = 3 for j = 2. p3 = 5 for j = 3, p4 = 7 for j = 4, p5 = 11 for j = 5, etc etc...

I just don't see how I can make use of this fact above. Any time I want to generate a prime, say the 7th, I will check by plugging in: 2(7)*ln(7) = 27.2427... But this is completely useless, as it turns out. This number is way bigger than the last generated prime in my array, which is logical. Hence I still have to resort to either brute force by checking the last prime+1 for mod0 with each of the primes in my array. The other option is to resort to already existing algorithms that reduce the time to polynomial time.

Can you show me how I can make use of that fact: p'j <= 2j*ln(j)? Thanks.

Answer 1

To show that I can generate a list of the first J primes in time polynomial in J, I need to work out the cost of however I am generating the list.

If I am generating the list by checking numbers one after the other and discarding non-primes, there are two parts to the cost of generating the list - how long it takes to check each number, and how many numbers I need to check.

If primes were vanishingly rare, then I couldn't afford to check every number from 2 on, because simply listing all those numbers would be too expensive. But if I know that the Jth prime is no larger than 2j*ln(j) I can at least list them all in polynomial time.

In fact, if I have to generate J primes, and I start by taking the first 2J*ln(J) numbers, and I decide to check each number for being prime by test dividing it by every prime found so far, I never have more than J primes on hand at any time, so I cannot end up doing more than 2J^2*ln(J) trial divisions. This won't win me any prize for efficiency or clever algorithms, or even sharp bounds for computational cost, but it is no worse than polynomial.

Answer 2

Maybe what's tripping you up is that you're thinking that the upper bound gives you a method to directly generate the jth prime, or the first j primes. It doesn't -- it just gives you a size limit on the set of numbers that you need to check with some method you already had lying around, e.g. trial division.

If I give you a list of the n-1 numbers 2, 3, ..., n and ask you to find all the primes in this list, you can do this using trial division in O(n^2) time:

1. For each pair of numbers x and y, just check whether x divides evenly into y, and cross y out if it does. This step is O(n^2), and requires O(n) space for keeping track of which numbers have been crossed out.
2. List out all the numbers that were not crossed out. This step is O(n).

Note that this finds all primes <= n in O(n^2) for any positive value of n. So in particular, if we are told some value of j, it will work for n = RoundDown(2j log j).

With n = RoundDown(2j log j), this algorithm runs in time O((2j log j)^2) = O(j^2 log^2 j), which is polynomial in j, and it must succeed in finding at least the first j primes, since the bound tells us that the jth prime can be at most RoundDown(2j log j), and we have included every number up to and including that one in our input list. (It may find even more primes, but we can discard them in linear time if need be.)

Exercise: Think about why we are allowed to round down here.