Ask a question

Find position of prime number

Your range only goes to ten million, which is small for this kind of thing. I have two suggestions:

1) Create a table of pi(n) at convenient intervals, then use a segmented Sieve of Eratosthenes to count primes between the two table entries that bracket the desired value. The size of the interval determines both the size of the required table and the speed at which results can be computed.

2) Used Legendre’s phi(x,a) function and Lehmer’s prime-counting formula to calculate the result directly. The phi function requires some storage, I’m not sure exactly how much.

Of the two, I would probably choose the first alternative given your problem size. Implementations of both the segmented Sieve of Eratosthenes and Lehmer’s prime-counting function are available at my blog.

On reflection, I have a third alternative:

3) Use the logarithmic integral to estimate pi(n). It is monotone increasing, and always larger than pi(n) over the interval you require. But the differences are small, never more than about 200. So you could precompute the differences for all values less than ten million, make a table of the 200 change points, then when requested compute the logarithmic integral and look up the correction factor in the table. Or you could do something similar with Riemann’s R function.

The third alternative takes the least amount of space, but I suspect the space required for the first alternative wouldn’t be too large, and sieving is probably faster than calculating the logarithmic integral. so I’ll stick with my original recommendation. There is an implementation of both the logarithmic integral and the Riemann R function at my blog.

Article source: http://stackoverflow.com/questions/14126959/find-position-of-prime-number

Comments are closed.